What are some fun setups for Dominion for two players?
Since random setups have already been recommended, let me suggest a couple of individual card combos that can form the core of an interesting set.

Option 1: Core strategies in the base set. Choose 2 of these, and fill in the rest of the cards randomly.


Woodcutter/Workshop + Gardens (+ Cellar): obvious gardens path
Throne Roome + Remodel/Mine: TR helps the fact that these strategies are slow on their own
Chapel: trash as fast as possible and race for provinces
Witch/Militia (interesting both with and without Moats): slow down your opponent with attacks
Smithy/Moneylender: accelerate the early game to 5+ coin hands


Option 2: Interesting card interactions in the base set. Choose one and fill in the rest randomly.


Witch + Gardens strategy cards: do you curse your opponent and make his/her Gardens more valuable?
Militia + Library: you can attack to slow down your opponent, but if he/she has a Library in hand then the attack is mostly wasted. Do you go for offense or defense?
Chapel + Thief: if you trash your starting cards to accelerate your deck, you will be more vulnerable to having your few (and good) treasure cards stolen.


Finally, if player interaction is a really important criterion for you, you should seriously consider adding the Intrigue expansion. Not only is it built around the theme of interaction, but it also has lots of cards that combo well with base set cards to create interesting strategies (Duke/Duchy, Gardens/Bridge, Gardens/Ironworks, etc.).