Actually, since Wild Shape is still limited by the hit dice of the druid, dire bears still do require 12th level druids. Dire tigers require 16th level.
That, of course, takes nothing away from their coolness.
Sadly, druids don't gain (or lose) hit points due to Con changes from wildshaping that I'm aware of.
As for my picks...
The good old wolf is a good one for having a nice ground speed. They move 50' per round, which is the same as a cheetah (remembering that Wild Shape does not imitate the cheetah's sprinting ability). Unimpressive attack, but then, that's what bears are for.
At early levels the black bear serves you well as a combat form...but do not neglect the croc! An ordinary crocodile has a 1d12+6 tail slap, or a 1d8+6 bite. Additionally they have better AC, and Improved Grab! The swim speed doesn't suck either.
Once you hit 8th level your combat wildshape quantum leaps with the ability to assume Large shapes. This opens up most of the dire animal forms, and 8 hit dice is enough to become the coveted Brown Bear. With a devastating full attack and a good grapple mod combined with Improved Grapple, this form will serve you well. The only one that really comes close for straight combat is the Dire Wolf. A good single bite attack combined with the fiendish Trip ability makes dire wolves deceptively potent.
While I lean towards bears and dire wolves, I feel I should inject a note of support for the tiger. Available at 8th level, the tiger can do a lot of damage on a successful Pounce (which as an Ex attack ability, you do get).
Also, if you have some space to charge, consider the rhino. Available at 8th level, it combines good AC (for an animal) with truly ungodly damage on a Powerful Charge attack. 4d6+24? Sign me up for that! Amusingly, while real rhinos are rather nearsighted, you even get a mild Spot bonus.
A last note: In addition to the burrow and climb speed, wolverines and dire wolverines have Rage as an Ex -attack- ability. This means that druids in those shapes DO get Rage. This makes an otherwise lackluster combat shape a bit more appealing.
From there your only real restriction on combat shape is your hit dice.
Other utility shapes include:
Ape (and Dire Ape) - Combining high Str scores with humanlike hands (and Reach!), these forms are handy for druids who want to fight with their weapons, arm wrestle, or perform similar tasks of manual dexterity and strength. Downside is the low AC, but your DM might let you get away with wearing your armor as an ape, in which case...booyah.
Eagle: Available right away and possessing a fly speed rivaling that of air elementals, the eagle is a -perfect- shape to combine with Flyby Attack and Natural Spellcasting. The mobility and relative immunity to ground attacks offered by flight serves even dedicated "caster druids" extremely well.
Horse or dog: These are two shapes that the enterprising druid can use to easily disguise him or herself within just about any society. These animals are so ubiquitous that they do not elicit comment or notice among most. Invaluable for the spy druid.
Snake (esp small): Also a good spying shape, mainly due to the good innate Hide skill and relative innocuousness of it. Of course, if someone DOES see you, they're likely to back off or try to kill you (eek! snake!), so do be careful.
Not too great for combat, but can be good in ambushes...remember the save DC of your venom is based on Con, so cast Bear's Endurance before striking!
Porpoise: One of the better swimming shapes, in terms of raw speed. Not much more to say.
Octopus: Aquatic druids take note! 8 arms, especially with some buffs like Bull's Strength, can add up to serious hurting in a hurry! This is especially nice when you have sufficient hit dice and size availability to become a giant octopus.
Orca and Giant Squid: Probably the best straight combat shapes there are for undersea action but it requires you to be able to assume Huge forms.
Overrated Forms:
Leopard - Basically a smaller, weaker tiger, the leopard suffers from a low attack modifier and low individual attack damage. While a successful pounce/full attack can still do damage, the odds of hitting much are slim, which kinda nullifies the point. By the time your BAB is high enough to compensate, you can turn into a tiger...which is superior in almost every way.
Cheetah - As noted, druids don't have access to Sprint, which makes cheetahs no faster than wolves and less damaging than leopards. Avoid.
Boar - While the AC is decent for an animal, wolverines are probably a better choice for the "maddened horror" category. While getting free access to the Diehard feat (via the Ferocity ability) doesn't suck, the Rage ability is a bit better, IMO.
Polar Bears - Not really any better than brown bears in 3.5. They have more hit dice, but that means nothing to a druid except that they're harder to turn into. The only thing they really have over brown bears is a swim speed.
Badger - Aside from being smaller and more easily overlooked (since they're more "normal"), there's nothing to recommend a badger over a wolverine or dire wolverine.
-- All of these are IMO of course.
