Firstly, make sure you get a table for two. You can always talk to people at other times but I think food is for enjoying and not for making small talk or listening to boastful conversations about previous cruising exploits from comparative strangers.
Decide what criteria you need. Large or intimate ship? Do you like a lot of entertainment? Destinations are up to you. Decide whether you want Canaries, Mediterranean, Greek Islands or further afield. Do you dislike flying? Then sail from Southampton ( or other ports). There is also the Baltic of course and Scandinavia, if you are not too fussed about warm weather and lots of time on deck.
We were, as you say, stuck with people on our first cruise but things have changed since then. Lots of lines have open dining so you sit where you wish.
One line we went with included shore excursions in the cost. It was small and described itself as a country house at sea. There were erudite lecturers,
Entertainment was minimal but good - a trio or quartet most days, plus lots of interesting talks, but the clientele were seriously on the older side. Peter O'Toole was a guest on one of our trips. Since then we have
opted for larger liners as they are more fun with varied entertainment and better facilities. Celebrity is one such, and most cabins have balconies, a feature well worth having. i gather they have relaxed the formal nights although these were never obligatory. Having said that it does seem that people enjoy dressing up.
I hope Galen comes on as she is an accomplished cruiser and don't believe what she says about mandatory and many strings of pearls. Not essential !
Do let us know what you decide.