I tried to paint the minis more Toy-ish so that it looked like a board game, but man no way, its more tabletop style and i painted the bases green with a grass style.
But instead of the bases you can see the different armies by theire colours.
Uthuk has much red on and Daqan has blue.
In my opinion black edges are just fine. To distinguish armies I would recommend using accent color on miniature itself. Just like Tom said.
But i think for Undead and Latari Elves it is not so easy.
With a proper mindset you could always use one color as "accent" and put it on mini