Recording phone calls/ Skype hardware?

I have a podcast where I’ve gotten some film makers interested in being interviewed, but the problem is that me and my partner on the show have a setup where we talk over Skype, but each record our own halves of the conversation locally using audacity, and then I edit both halves of the conversation together.

Both of the film makers I have signed onto the show right now though, don’t have skype and don’t seem too computer savvy. They are down for a telephone interview, but I don’t even own a landline (I’m 27, and move around too much, this is the first time in adult life I’ve ever actually needed a landline…)

So I have myself, my partner in another state (computer savvy) , and an interviewee who needs to be called over the phone, what kind of hardware-software combos could I use for recording this? Extra points for having good audio quality and being cheap.

Thanks!

Google Voice has the ability to record both sides of conversations.