UK reply.
http://www.noble-caledonia.co.uk/ is a UK company that specialises in small ships. Completely different experience to the BIG cruise lines and Giant ships! Most ships have about 100 guests, Yes they are more expensive but you get what you pay for!
They are not floating gin palaces with masses of entertainment (and queues!) and they keep away from the tourist trap ports.. Their main attraction (apart from the lack of the masses) is the itinerary.
For example last November we were in Antarctica in the most breathtaking scenery on the planet! Not a hot Caribbean island but icebergs the size of 10 city blocks and millions of penguins!
In August we were out in Zodiac inflatables drifting with a pod of bubble feeding humpback whales in Alaska and then standing in a salmon stream with the fish running through our feet.
Or you could visit the Baltic and experience something completely different for Americans, European and Scandinavian culture! St. Petersburg (Russia) would blow your mind!
These itineraries may not be to your choice but I am sure you could find something that is very different to the packaged big ships!