There are many cruise lines you can choose from,try to be in madeira for new years eve by doing a canaries cruise we did it on tompsons destiny it was just brilliant the fireworks at midnight are just amazing go and have a superb time.
Fred. Olsen have three Christmas/New Year cruises in 2008, one from Dover, another from Southampton the third from Liverpool all to the Canaries. I went on one last year and had a great time.You are spoiled for choice. Bon voyage.