oh the many many hours my family have spent on this game... and HoMM 2 and 4.
I would have voted for conflux because magic elementals might as well have been a top tier creature. they are basically hydras that move across the map and are immune to magic. Phoenixes are a rather underwhelming top tier creature but if you manage to keep them alive long enough you'll have dozens before anyone else has 10 of their own top tier, being immune to fire doesn't hurt (har har i'm funny) though their rebirth ability sucks (entire stack has to die before it happens).
never had much use for energy and magma elementals (which would have been very dwarven of a choice since when it boils down to it, a large stack of those really does solve all problems).
Conflux is one of the best you can choose for early army strength. Pixies once upgraded into sprites are incredibly numerous (like imps), incredibly fast (more-so than centaur captains) and cant be counter attacked (better than you think, amazing if used right). I love this unit because once you cast bless on it (a very early game spell that causes the target to always do max damage) they become quite deadly, something most tier 1 units never become (gremlins, skeletons and centaurs (to some degree) excluded)
Conflux's second tier unit, the air elemental is useful early on because it has a moderate speed and takes very little damage from ranged attacks. They are some of the best tier 2 units in the game before they get upgraded to storm elementals which are only tier 2 creatures because conflux cant have two tier 3's. Storm elementals retain all the strengths of being air elementals while gaining a ranged attack and having a ranged attacker who is immune to lightning and chain lightning is
always good. Speaking of which the water elemental is pretty sub-par until you upgrade them to ice in which case they basically become storm elementals without the immunity to lightning (but they are immune to ice bolt... assuming your enemy never managed to get anything better)
my second choice would have been the tower nation. I love ranged units and they get 3 of them (including their tier one and top tier units). Their master genies are also pretty useful, not just as a fast and hard hitting flying unit but they can also cast a random benefical buff on one of your units on command. If you cast bless on your gremlins then the genie casts say precision on them, they will be pretty powerful. I never did find golems, gargoyles or nagas to be very useful, probably because all the carnage the three ranged units could toss out.
Necropolis can make for an interesting game. Protect your skeletons and liches. With necromancy and careful first few months of rampaging you can quickly have thousands of skeletons while inferno players will have only a few hundred lousy imps. Bone dragons and liches are fun too.
I dislike inferno because with the exception of some kick ass last few tiers, they really suffer from army strength. Imps are laughable, requiring you to have the holy grail for them to finally have a use (that's a pretty steep requirement seeing as how finding the holy grail early almost never happens.)
Magogs are... not so great. Usually i love ranged units but a ranged unit with an area of effect attack only really works for the liches (friendly fire is a bitch). Tiers 3-5 are pretty generic, mostly medium movement with average to above average attack and health. Cerebuses (sp?) are kinda good, spread attack (with no friendly fire) without counter attack and really nice movement, however unlike the sprites, they don't fly and tend to be attacked more often (computers at least see them as a moderate threat, compared to sprites which are often ignored). Inferno's ifreet and devils are what really make this nation playable. Ifreet are flying tanks that are immune to fire and enemies that attack them in melee take damage based on how many ifreet you have. The devils (once upgraded to arch devils) have a lame summoning ability but ignore that. Teleporting and extremely high speed makes them first turn assholes. Use them to take out a chunk of the enemy's most valuable unit.
castle and rampart nations are also pretty nice. castle is great for mobility and ranged damage (take care to abuse the champions ability to increase damage based on how far they move that turn, arch angels are basically arch devils that can raise dead units and zelots are really powerful if you get their numbers up. Rampart has a very strong low level archer and a decent first tier creature. dwarves and treants are best left at the fortress which leaves your traveling army somewhat weakened, makes your "defensless" castle a little harder to take without an impressive army or an awesome spell or two. peguses and unicorns are so-so while their top tier is really expensive for their stats. sadly gold dragons are not immune to implode like black dragons are. Rampart is a great nation to mix and match armies. Toss in marksman and zelots from castle or gremlins and magi from tower.
I think I have posted enough wall of text for now...
Will be watching.