I like Empire a lot. It is effective, looks good, and can be configured in many different ways using lots of relatively inexpensive plastic figures.
However, part of the answer depends on your own personality. Are you a beserk attacker, an out maneuverer, a stolid defender, a tricky counter-attacker, or just warped and twisted sneaky? You need an army that matches your personality for a first army.
If fierce attack is your thing, Dwarves and Wood Elves are not the answer.
If dogged defense is your thing, forget Elves or Undead.
Orks and Goblins and Lizardmen are nearly as flexible as Empire, but completely different.
I run Vampire Counts and Empire and may add Khemri, Dark Elves, or even Orge Kingdoms for a joke.