Costa Rica (Bahia Salinas) is great , I was there 3 weeks ago and had a blast........ it isn't cheap to get to from Canada and conditions were not easy either when I was there. It was however great fun and there are direct flights to Liberia which means you don't have to deal with US immigration either. Hatteras would probably be cheapest if you share a ride down and a house but I'd not go till 2nd week of April just to make sure it's warmer.
Value for money and good conditions/warmth I'd say Cayo Guillermo Cuba would be your best bet
loads of people go from Montreal and there are some instructors from here who go down with clients to teach as well .......... p.m. me if you want more specifics.