Realizing this problem, I started researching how to improve usability. I started to think about several games that did this very well. One often cited example is Portal, in which almost the entire game is a tutorial, yet it doesn't feel that way. Each level adds a single new element which you have to overcome, and shows you the basics of overcoming it. Then once you know that, it has you test your newfound skills.
Other games will simply start out with an extremely reduced functionality, and improve it. Kerbal Space Program's new Career mode is actually quite a bit easier to learn the game than the sandbox mode, because it gives you limited functionality to start with, fewer parts, and gives you missions to help you learn basic skills before you proceed to the more advanced ones.
The second problem was straightforward. I added logic such that if a player clicked on the ship then city, then they would automatically go to the city, and bring up the dialog when they arrived. This worked well! The first problem was a bit trickier. There are a number of ways to make this easier, I chose to simply highlight the ship. The ship will change color to red every few seconds for about half a second, drawing attention to it. Then once a user has done that, then the nearest city will blink similarly red.
I should add that before I chose to turn it red, I tried a different scheme, causing a glow to appear about it. That proved too subtle, people who weren't looking for it just ignored it. I was careful to not tell the users anything other than it was a usability test, having a bind test was important.
Lastly, I gave this to a few people, and asked them what they though. They noticed the blinking, and it started to guide them along the path. I know now that I still haven't really taught my users how to play, but I'm making progress towards that end!
Bottom line is, test for playability frequently. Help the user each step along the way to learn the game. If at all possible, make helping them use the game feel a part of the game. Do this, and you will have success!
Ben Pearson is the author of the Amateur Radio and other technology blog KD7UIY and developer of Games and Apps at Google Play pearsonartphoto, where he plans to publish some of the games created by inspiration of gamedev.tv. He is currently working on a Sea Trading game, which you can subscribe to updates at his Google Group. He has been a programmer since a young age, although only recently is learning programming with game engines. He has completed the the Complete Unity Developer Course and the Procedural Generation courses, and is working through the Complete Blender Developer Course and Unity Game Physics courses. He is hoping to soon start Unreal Courses soon. Follow him on Twitter @KD7UIY.