This isn't a problem of 'grass is greener', its an issue of you being young and wanting to discover yourself and the world. Nothing wrong with that. In fact, its something you owe it to yourself to do.
"Grass is greener" is a problem only if you are constantly changing partners, jobs, homes, and zip codes. And also if you have passed a certain age where "youth" doesn't cut it as your excuse for instability. But, it doesn't sound like that's what youve been doing.
It sounds like youve travelled a lot already and gone outside your standard context. The fact that you want more and even said that you *need* travel are big indications to me that you should make the plunge.
Seriously, don't wait and regret it. If you do it and realize big city living or whatnot is not for you, its not a waste or a regret because its something you must do in order to find out.
Hop, hop, hop - you have to make your own life and figure out whats best for you. So make the move!