WoW newbie looking for advice

[Lissa]

Um, so after getting my Voidwalker at level 10 and playing until 11, I got kinda bored and at the same time curious about the other classes and races. So I went on an experimentation spree. I now have a bunch of level 5-8 characters for all the classes and most races. Now the dilemma is that quite a few of them are fun to play, yet I can't see myself devoting time to even two at a time. I find myself liking the tanking power of a Warrior, but I miss the ability to self heal that I had with a Priest (speaking of which, they actually gave Priests some real offensive power in WoW!).
I love the amazing power and range of the Mage but hate the downtime (mana regeneration) and extreme vulnerability. I love the sheer damage potential of the Rogue, but stealth seems so awkward (having to manually unstealth behind a monster to do a backstab got old after the 10th time).

You don't have to unstealth to backstab. Just hit the backstab button from your stealth bar and you'll backstab from stealth.

So I'm leaning toward switching to a "jack of all trades" type character. Which leads to me either a Shaman, Druid or Paladin.

The Druid is out due to choice of races. I can't stand the Night Elves or their starting environment and lore. And while I love the fuzzy Tauren, they're just so huge I can't even see my target when in melee!

You can move your camera angle around so you can look from different angles so you can see your target. As you level, the mobs you fight will get bigger in size so even a Tauren will be looking eye to eye with some mobs (or looking up in some cases).

The Shaman seems to lack melee attack power, even with enchantments. Does it get any better? How are they in terms of solo leveling? How about late game?

Yes it will. Shaman can kick out a tremendous amount of damage at higher levels be it in melee or casting. Elemental tree is the casting tree and Enhancement is the physical tree with shocks through in. Eventually, usually around level 40, the Enhancement Shaman comes into their own with damage when they can dual wield.

Which leaves me with the last option. Paladin. How effective are they later on? For the first 5 levels I used a Human paladin he breezed through quite easily. But does this continue to hold up?

It depends on what spec you follow. If you go with the Retribution tree your damage is very spikey. Case in point, my Paladin had wildly varying kills on mobs where I would kill one mob in under 10 seconds and the same type of mob would take 40+ seconds to kill all due to whether I proc'd Seal of Command or not and how many crits I got. Retnoobs, as people refer to them, are probably one the most inconsistant damagers in the game swing to swing. Other classes you will see pretty stead DPS outputs, but with Retnoobs you see large peaks and troughs in your damage.

Another option for leveling is going Protection when you can get the Reckoning talent. Again, you will see variance in your DPS, but not as drastic as a Retnoob. You will be slower in killing unless you get crit a lot and you can take on a lot more mobs at once that the Retnoob can't. Also, at high levels, the Protection Paladin probably becomes one of the better grinders in the game due to the sheer fact that you will pull in large number of mobs and be damaging all of them at once with little incoming damage to your self (due to wearing plate and have very good tanking skills from the Protection tree).

Lastly, I also got an Orc Hunter to level 8, and then find out I have to feed my pet to keep it happy, and level up too? The sounds like too much of a chore. Please tell me that isn't so, because frankly I actually enjoyed the versatility and power of the Hunter, at least in these early levels.

Eventually you don't really notice the need for feeding, you'll just toss food at your pet every so often. What will wear on you more is the need for a quiver or ammo pouch so you can carry enough ammunition with you. In having said quiver/ammo pouch, you lose a bag slot which means you only have 4 bags to work with.

One of the most disappointing things was finding out that dual wielding isn't available until level 20 (!). Way to delay the fun, Blizzard. Oh wait, this is an MMOG we're talking about.:)

The only class that gets dual wielding pre-20 is Rogues and they need it. Most Hunters use a two handed weapon for raptor strikes shifting to dual wielding only when they can get more effective stats from the two one handed weapons than the single two handed weapon.

And these are Triggerhappy's adventures thus far.
P.S.
Where are the alliance and horde auction houses? I managed to accumulate 42 silver (probably a pathetically laughable sum for you folks) and want to at least see what's available there.

all major cities have an auction house, just ask a guard and they'll conviently point you to the one in the side and mark it on your minimap with an arrow point towards it if it's not on your mini-map aready.