You could mitigate bad starts by one of the following (maybe as option):
- Reveal more of the map around the start point.
- Reveal the closest n resources, but not the terrain around them
- Reveal random patches around the start point
All these should, of course, apply to the player and AI.
The game is great, I just thought I'd pitch in my two cents on the topic :)