Go to www.cruisecritic.com and read the expert review of each cruise line. That will give you an idea of the fit for this couple and then you can look for cruises from there - that's what I'd do!