I'd far prefer to solo on my DK or even BM hunter than a paladin or druid :p
Really though, there's no achievement you -need- to be a solo capable class for...it's faster to grind exalted raid reps etc in a group anyway :P
So really, the best achievement hunting class? I guess the best way to figure it out would be go tab by tab and picking the achieves that some classes have an advantage for.
General tab, well, with rumours of 150 mount achieve coming out, I'd make something that gets free class mounts - so DK, warlock, paladin. Especially on a new alt that won't have any of the retired mounts, I'd be making an engi/tailor and one of those classes.
Flying around hugging critters/killing pests? 20% mount speed, paladin or DK. Slightly faster than any class with the guild perk.
Quests, really the only advantage is again the slightly faster movement of DK/paladin.
Exploration, again, faster movement.
PvP...meh, any class that has a genuine advantage there will probably be nerfed by the time you level it. Go human for the racial perk if you're planning on grinding exalted WSG/AB.
Dungeons/Raids...It's faster to do all your rep farming in a raid anyway, so no class really has an advantage unless you're on a low pop server. Tanks I guess may have a slightly easier time forming achievement runs.
Professions? Faster flight again, solid deal, helps with archaelogy/winning fishing tournament/flying everywhere for the dailies in outland/northrend. Dwarf for professor title, I guess, although it's ridiculously easy since they added the new rares.
Rep? Human anything clearly helps.
World events? Again, mostly include a bunch of flying all over the place, faster speed.
So really, I'd say overall, you should make a human paly or DK. They have the added benefit of being amongst the best solo classes for any raids you can't get a group for.