Piranha,
Your ruins suggestion is a good idea. Even with more initial starting units, early ruin allies still matter a lot especially if they are the ones that provide some kind of stack bonus and especially if you get a lot of those allies. Even in DLR where players got more units, early allies were a big deal. So when DLR was patched players wanted defined benefits as much as possible instead of random ones to reduce luck where ever possible. My suggestion about heroes+allies comes from what was done on DLR.
I think you can still afford to give a player a small amount of gold (250-500) or 3 turns worth of allies (basically 1 ally) in level 1 ruins. That's not over powering. Then your level 3 gold/allies could be level 2 and you'd come up with a bit more gold/allies for level 3.
One thing I would like to add is that in Warlord IV, ruins have the ability to regenerate during the game. There is a 1% chance per turn for each searched ruin (so if there are 10 ruins that are searched there are 10 rolls made at 1%) to regenerate itself (basically a new monster takes up residence and there is a new reward). The regeneration takes place at the start of the next turn. I think this would be nice to have because it means you in theory never run out of ruins no matter how long the game goes.
KGB