gempukku.com/gemp-lotr
That's the site where you can play online. There are many different formats for this game, and the deck builder on that site will help you filter the cards so you can find what you need for the format you're using.
There are lots of decks that use Gandalf, either as a supporting character or as the main driving force of your deck.
It's great that you like all those different characters, but there is a problem. The very nature of this game makes it so decks work better when you focus on only one or two Free People's cultures, in addition to your ring bearer. "Rainbow" fellowships are really only viable in Fellowship Block.
As for liking Sauron and the Witch-king, you probably won't be able to use them in the same deck. They are some of the most expensive minions in the game, so you will rarely be able to have them both in play at the same time. And like I said above, mixing Shadow cultures isn't a good idea except in specific decks.
Anyway, pick a format you like and learn the cards that are available for it, then make a deck and try it out. You can always find someone to play on Gemp.