Hey Yankee,
I'm in Virginia Beach, VA, Mid-Atlantic Coast and I paddled this weekend with 41 degree water and about 46 degree air temp. I dress in case I have some kind of catastrophic failure and am floating in the ocean......I wear an O'Neil 4/3mm wetsuit, 7mm booties, 2mm gloves and a hood. Plus the PFD and leg leash. You will be more than surprised at the wetsuits they are making these days. They are sooooo stretchy and comfortable it's like having nothing on almost. The technology and good rubber/neoprene is just awesome and keeps you very warm. I surf in these suits as well in the cold water and have been out in the water surfing for 2-3 hrs, no problem.
It sucks wearing all this rubber, but what else you gonna do, go to the gym ? No disrespect to anyone, but I hate the gym and would rather get my work-out in the water.
I got my 4/3mm O'Neil full suit for only $179 at the local surf shop, not bad at all, and that's O'Neil's bottom line suit, they have other 4/3 suits warmer and even more flexible for more money.....
Happy paddling!
-Rich