As already mentioned Nihongo con Teppei for beginners is really good, he also hosts three other podcasts:
- Nihongo con Teppei - A podcast for intermediate learners.
- Japanese with Teppei and Noriko - A conversation style podcast with Noriko, the host of Learn Japanese with Noriko. The audio quality improves a lot at/around episode 14.
- Eigo con Teppei/ELCT吉祥寺de英会話 - This is more tailored to Japanese speakers learning english.
Other great podcasts:
- 三本塾Sambon Juku Radio - This is on YouTube, but you could download the audio (it might be on last.fm as well).
- Hapa英会話 Podcast - This is a podcast that teaches English to Japanese speakers and it’s really well structured.
- JLPT Stories - This is a podcast that is tailored to learners planning on taking the JLPT and ranges from N5 to N1 listening. They use both male and female speakers.