We did a supported tour in and around Quebec City in 2006. You rarely hear English in Quebec City and it really felt like I was in Europe. It was awesome. I think it might be pretty cold there in April, though.
My anniversary is in December. For our 25th, we did a bike trip to the Czech Republic and Austria. But, we waited until the next summer. Maybe you could plan some local things for April (DelMarVa sound great) and a bigger trip later on.