I bought a lightly used tandem last spring at the local bike swap. It's a basic level Trek, but not a bad bike at all. It came with lower level (but well functioning) Shimano components, and was the right size (med-small), and was about 1/2 normal local price so I bought it for $500US.
Although you don't have a good selection in local shops, keep your eyes open, maybe even post some notes in places cyclists look. A tandem, especially an entry level one, is something people buy, use 10 times and decide 3 years later they might as well get rid of for 1/2 what they paid for it.
It is fun. There's a little technique involved but nothing that 15 minutes in a large empty parking lot and then a couple of easy rides won't teach you. There is a tandem forum on this board which is where I got my advice last year.
The reason we enjoy it is that it really is the only way we can have nice rides together. I'm no animal, but I just ride stronger and faster than she does. The tandem is the great equalizer. We can ride routes that she can't ride by herself (I horse it uphill), and we can talk pretty easily through the entire ride.
This bike is MTB style: 26" wheels, MTB handlebars, etc. The only things I changed are: changed front bars to a more flat bar w/ bar ends. Put our own saddles on it, changed big 2" knobby MTB tires for 1 1/4" slicks (~32mm tires). The stoker seat post is suspension type which I think is important for the stoker's comfort.
I might toy with changing the front end to drop bars if I can find the brifters at a good price, but for now, it's OK.
One word of advice which you will hear from everyone, but it really can't be said enough: keep your stoker happy. Don't go faster than she wants to, or further. Make sure she has a comfortable seat, etc. Don't do anything, ever, to sour her. Like teaching kids things, it's much, much better to under-do it than over-do it. It's much better if they feel like you're quitting a ride too soon rather than too late.