As a podcaster I can only speak for myself...I initially started out with a very basic telephone setup. I still have the old box somewhere that records a phone conversation. This is the kind of thing radio stations always used and so I thought at the time it was the way to go... I was wrong on that one. You can get a much better recording on Skype if done correctly and using the right programs.
 
In terms of quality my show has been a learning experience and Dave is correct there is much audio editing involved. I usually know within a few minutes if there's  going to be a lot of editing involved. The shows that sound like they weren't edited really were. If you heard the uneditied show it would have REALLY been bad..and my first shows were terrible admittedly because I was still learning. Subsequent shows have been better but not perfect. One thing that makes a huge difference is if both parties  use a decent microphone and interface. I can't control everything done on a two party show. In some cases it is mandatory that the other party use a phone line and a typical phone...so quality will always suffer there, although for only voice it can still be done well if mixed properly. In a more controlled and regular situation...like a regular show with the same people it's a lot easier to get better quality because you can pre determine the setup. If the engineer can have a high quality audio file sent from the guest this makes it even better...but all of this is usually a pie in the sky dream and the reality is that I usually deal with what I am dealt.
 
There was a time when I uploaded at lower bitrates, but my server/host now allows me to go with a better file, so I am now uploading a 320 mp3 file in stereo usually and this is really only for the intro music since the dialog need not be in stereo...at that bitrate it's possible to get a really good sounding show if you can get a nice phone conversation...I've never not posted a show, but there were a few  I should have omitted based on the horrible phone connections.
 
It's usually never the same challenge...and it's a lot of work for no pay ;) So you need to enjoy it as a motivation.