I recommend cheese with deeper flavor such as sharp and mild cheddar. In terms of ease of use and convenience, I find that cheese slices are the best! They easily melt and don't harden when the bread cools down.