In Stockholm, Sweden:
I prefer paperback books, and Pocket Shop (a former employer of mine) is my first choice. The chains has stores at Arlanda and Central station, but my favorite one is located at Götgatan in Södermalm (Subway station Slussen)
If you’re at Götgatan, don’t miss out on Söderbokhandeln! It’s one big room (aka small bookstore) filled with all the books you can think of. Mostly in Swedish of course, but ask the store keepers, they’ll help you find something good! They also hold a lot of readings and author meet-and-greets. As said, don’t miss it!
If you’re at the other end of the city – a proper bookstore is Hedengrens at Stureplan. (Subway station: Östermalmstorg) Located in the Sturegallerian, I don’t visit it as much as I should, but it is really worth the time! Work your way down the stairs (that is also a gallery…) and browse the books in English, or maybe Spanish or German. Definately the place to go if you want international books, and a wide varitey of such!
At Drottninggatan 9 (just a block or two away from Gamla Stan/”Old Town”) the store Bok & Bild is located. This bookstore has a pretty odd selection of books downstairs, and the personel is generally extremely helpful. A lot of Swedish books of course, but I think you might find a gem or two anyway!
Whenever in Paris, France:
Shakespeare & Co – This place is truly a piece of heaven! The shop is small, the books are high and low, and during the evening you can find performing artist in front of the store.
The bookstore was founded by George Whitman in the early 1950′s (originally Le Mistral) and the history of struggling writers finding inspiration and a haven there is worth a visit in itself! My Shakespeare and Company visit always include a sit downs upstairs and outside overlooking the Notre Dame
Please check back at any time – you’ve ain’t seen nothing yet 
