Why not just get a 100% poodle! Of course the folks here know that I am a bit biased when it comes to poodles. I have a Standard who weighs in at 50-55 lbs. and, having had a golden, you know they are even larger. Allow me to suggest a miniature poodle. They are on the low end of the scale that you are looking for. My Ripley, a miniature, weighs 14 lbs. and my former miniature was 18-20 lbs. I, too, would suggest taking a look at shelters first. All of my previous poodles came from breeders and Ripley is my first rescue but he will definitely not be my last. Good luck on your search!

There are lots of cuties here: http://www.petfinder.com/shelters/FL442.html

This little cutie is already housebroken. That would make life a lot easier than tryinig to train a puppy on a boat.