1) You can find remotes on Ebay too. The car is programmed to accept the remote. The remote only sends a signal and is never programmed. This means that on cars like yours and mine, multiple cars can be unlocked with the same remote. The programming instructions are on this forum. Do a search, and if you search my username they will come up somewhere.
2) The Nakamichi system wouldn't be able to control your cd changer. Do you have a changer in the glove box? We have the Pioneer system and I've always been happy with it. The subwoofer makes a big difference. Otherwise you should be able to install the Nackamichi system and hook it up to your speakers. The connectors may be different though. This may have been covered elsewhere on the forum, so I suggest another search.
3) Converting from the fruity metric units, you're getting 19 mpg, which is a little low. We typically get 25 mpg, which is around 9.5 l/100km.
4) We'd have to know more about the specific conditions. Under light conditions below freeway speeds, what you describe seems typical.