You need to be at the edge of your current location to cross terrain into the adjacent square, if you aren't. But there may not necessarily be another city in the adjacent square. Ground travel isn't used much, so unless you really need to cross terrain (which takes over 12 hours), it may be best to wait for your faction to pick you up and take you to a ship.