The earliest one I have been able to find is RPGMP3.com, with their "World's Largest Dungeon" series that started on Sep. 24, 2004. Not too long after the podcast term was coined. And they're still uploading recordings!
In researching this I found some runner-ups:
All of these podcasts have since ended, but All Games Considered was the longest running of these, ending on Aug. 02, 2018.
Another one that came up was The Harping Monkey's Round Table Podcast, but the earliest episode date I could find for it was Episode 14 on Dec 02, 2005. As such, I think it unlikely that Episode 1 was before RPGMP3.com's 2004 release.
Interestingly, it wasn't until 2007 that "Best Podcast" became an award category in the Ennies (it went to Have Games, Will Travel).