What is the best technology (ease of use, clarity of sound) for recording phone interviews for podcast?

I like using Zencastr. It's always worked well for me, as it records a local version of the audio on the guest's side of things and automatically uploads it so I can download it. It's identical to just having the guest record using some local software and then getting them to send it to you. That'll usually be higher quality than recording whatever comes over the wire.

As for your side of things, I don't think the software matters. Whatever software you use to record should be fine. It's more about your mic quality, background noise, etc.