I have great fun singing "Transvestite" ballads - you mentioned "When I Was a Fair Maid..." - it has both a sailing and a soldiering version; the soldiering one is usually titled "The Female Drummer". Others include:

Sovay/Sylvie - I like Martin Carthy/A. L. Lloyd's version best; it can be done in neat close harmony
Jackie Munroe/Jackeroe - lots of versions!
Willy/William Taylor - again, lots of versions, some with Irish fol-lol-diddle choruses
Martinmas Time - border ballad w/right-fal-leedle chorus; recordings by Anne Briggs and Andy Irvine
Canaday-I-O/Wearing of the Blue - sung by Nic Jones, stolen by Bob Dylan, printed in Sam Henry's "Songs of the People"
The Male/Female Highwayman - by the inimitable Kipper Family of Trunch ("I can't make head nor tail of it...")
The Female Smuggler
Peter Street/Patrick Street/Barrack Street - the flip side of transvestitism, caused by a felonious female...

These are all fun if you're the "chick" singer in a guy group!