Fred. Olsen ans Saga hare single cabins and "singletons" are made very welcome. Fred. Olsen also have the option of cruises ex-UK and fly cruises. Try them.
I travel as a single all the time with P&O. But, to get the best deals on single occupancy, you need to book very, very early. I have just pre-registered for November 2009 with a cruise agency. The later you book the higher the single supplement becomes. Also don't assume that because other lines have single cabins they offer the best deal, this not always the case, and single cabins tend to sell out well before twin cabins. Please phone a cruise consultant and ask for their advice, and good luck.
It depends on your age and what you are hoping to do on a cruise. Check the cruiselines own websites for facilities, entertainment,nightlife (or not)etc.