My wife and I will be moving to Stockholm for my job in May. We're currently working with a relocation firm to procure housing (likely small - i.e., 1BR apartment). For a young couple (i.e., 30) with no children, what neighborhood would you recommend in the inner city? We're looking for access to parks, potential water views, fun restaurants, shops, and bars.
I can highly recommend looking at Solna, it's a great neighborhood which is very near to downtown and quick to commute. It's very green and has nice restaurants and shops. Apartment prices in Solna are also not nearly as inflated as other parts of town.
Realistically, as an expat you'll have a very difficult time finding a rental apartment in Stockholm, so buying a flat is probably your best bet (if you can afford to do so). The process is not as scary as it sounds, but also is more involved than I care to go into for this answer. :) At any rate, hemnet is your friend, be sure to spend sufficient time researching the different neighborhoods.
Also, if you are working downtown, you should search for flats which are on one of Stockholms metro lines (tunnelbana). The commuter trains (pendeltåg) run much less frequently, stop running sooner at night, and are more prone to disruptions during winter.