I'd be interested in cards that only do things when they're paired up with certain other cards. It might very well not be a good idea, as it might change the feel of the game too much, but maybe it would be worth experimenting with.
I'll call this card type "Ingredient," a term I carefully considered for 10 seconds before deciding on it. The idea would be that, when using Ingredients, all the Ingredient piles would be set out in addition to the normal 10 kingdom cards.
I'll illustrate what I mean by using spices for card names. (I take no responsibility for how nasty some of the flavor combinations sound.) Note that this is NOT an actual proposal that I would expect to be balanced or usable -- it's just an illustration of the mechanic itself.
Cinnamon
$4 - Action/Ingredient
Play another Ingredient card with this.
If it is Nutmeg, +$4.
If it is Basil, +3 Cards, +1 Action.
If it is Rosemary, +1 Buy, +$3.
Nutmeg
$4 - Action/Attack/Ingredient
Play another Ingredient card with this.
If it is Cinnamon, +1 Buy, +$1. Every other player discards a Copper or reveals a hand with no Copper.
If it is Basil, +2 Cards. Every other player discards down to 3 cards.
If it is Rosemary, +$2. Every other player gains a Curse.
Although this idea does involve an element of drawing luck (similar to Treasure Map and Tournament) to pair them up, there is strategy as well, because if you draw two Ingredients, there are two completely different ways to play them (that is, they do different things depending on which one you play first), and if you have three separate Ingredient cards in your hand, there are six different possibilities.
Like I said, my actual examples here are probably broken, but it's possible something could be done with the mechanic itself.
Edit: You could "spice" the idea up a bit by having some ingredients be pricier than others, but with more powerful behavior when combined. So a couple of cheap ingredients may only offer a modest gain; a couple of expensive ones do wonders; a cheap one and an expensive one does something in between.