Well, I didn't really restart at the begining much at first (though with each game, I would restart after getting so far). When I did, it wasn't so much of a bad starting position that bothered me, it was the maps themselves. I can never seem to get a decent map that suits my taste. I also noted after several reloads that the maps are always the same rough layout for each script. THAT gets boring to me after a while.
My first full game was a custom continent script that put me on a central island with a couple of other nations. It was me (America) , the Romans, The Arabians and the Chinese. Spain, England, Japan, and somebody else (I don't remember who off hand) each had their own islands in the corners of the world. After completing, and starting a new game with the same map settings (playing as the Romans this time), the map layout was the same.
I wasn't happy with the output of the other scripts either and got frustrated with the worldbuilder for creating maps. Another thing I look for is mountain ranges. If mountains are impassible, it really cuts their strategy if their are no good sized ranges around. Even using the Highlands script didn't help much. Finally, I through together a huge map that is loosely based on Earth's layout. I used a combination of YAME and WBS. YAME to layout the land and place the terrain and starting positions, and WBS to place the features and the resources as well as to tweak the rest (not AS bad when the foundation is already set). I started a game using the BH mod, but didn't like how that mod was working on it. So, I created my own mod (a very simple mod) and I am getting ready to play it out within the next couple of days. I still have some tweaks left before I begin and I want to Journal my campaign for future sharing...