1) Cecily and Gavin are probably my favorite medieval names. They're still sparingly used today which makes them recognizable but they both have that old timey feel.
2) When it comes to romance, I love it when two characters start as friends and slowly start the feelings train. A lot of romances are rushed (I'm guilty of this as well) and it often seems unrealistic or like the story goes on hold for the romance. The romance should be woven into the story carefully so the plot and the romantic subplot don't compete, but rather work together.
3) It's not all medieval, but Black Adder is a good one.
4) I love medieval stories so absolutely! Good luck!