Start on "Hero".

The map generated for me is so bad that I'm just stuck on a small island, and besides overpowered level 4-5 units, there's almost nothing else there.

I always play on random maps without water (I have to play very often to test the NHF mod, very often against 3 or 7 computer opponents in an alliance). I advise you to remove water in the generation settings and avoid putting yourself in dead-end situations.