Find Your Cruise
You don't say your age so although Fred Olsen does have a great reputation for 'us' of a certain age, but would not be a great choice for a young family with kids or the 20 to 30 somethings. Cruise tours are always expensive whichever cruise line you travel with, so take Aldrich's advice, & with the exception of St P'burg, research which trips take your fancy & be aware that every taxi driver will know every cruise tour by heart & negotiate at about 25% - 30% of the ships price.
No need to get 'stung' for shore excursions - it is easy do go it alone in port. Only exception to this is in St Petersburg where it is nigh on impossible unless you speak Russian! I would suggest taking a private Russian tour there - I would recommend alla-tour.com highly. For other ports i suggest you type 'baltics cruise message' into a search engine and click on the first link that comes up begining with 'northern europe and baltic' - very useful. As to weather, the North Sea was like a mill pond when we came across it. You never can tell. Personally the newer bigger ships tend to fare better than the old ones belonging to FO. Have you looked at RCI Jewel of the Seas, nice size and beautiful layout.
Of course, we lovers of 'smaller' ships can experience travelling through the Kiel canal across northern Germany on the way to or from the Baltic whereas the floating shopping malls have to take the long way round! ;-).
First, the North Sea: We've crossed it eight times on Fred Olsen ships and it's always been reasonably calm - perhaps we've been lucky - and the Baltic should be very smooth. Second, you won't get 'stung' with Fred Olsen - the only thing you pay for on board are drinks from the bar. Excursions will cost from around £30 per person for, say, a coach tour around Oslo to around £80 for a day's visit to Peterhof outside St. Petersburg (well worth doing!).
We haven't tried FO but our first cruise was on Ocean Majesty and we loved it. Most guests of retirement age, but others much younger. Our dining companions were a couple in their thirties and an other couple in their seventies (we are late fifties). We have never had a bad North Sea crossing and once you are in the fjords it's beautiful and calm. The Kiel Cannal cuts out a portion of the North Sea crossing to the Baltic. We had slightly rough seas between the Cannal and Stockholm but nothing to upset me and I'm a poor sailor. Friends who sailed on Calypso, when she was with her previous operators couldn't visit Tallin because of bad weather, but that was quite late in the season. I'm sure you'll love cruising. Wherever you go, have a lovely time.