Gene, if you look a little closer at your pairings, they're a little less "weird' than you think.
Traditional creamy cole slow is pretty much just cabbage and mayo and creamy potato salad is potato and mayo, so really, all you're talking about is cabbage, potato and mayo. You don't get any more of a classic food combo than cabbage and potato.
Toast dipped in OJ sounds a bit interesting texturally, but, from a flavor perspective, millions of people around the world enjoy orange marmalade on toast.
It's a bit of a stretch, but if you modify the corn a bit and make a tortilla, corn and cheese is all over the place in Tex Mex cuisine. I've also seen corn and paneer in curries- Paneer and cottage cheese are extremely similar.
For me, I like pepperoni and unsalted peanut butter.