O primeiro que eu pude encontrar é RPGMP3.com, com a série "A maior masmorra do mundo" que começou em Setembro 24, 2004. Não muito tempo depois que o termo do podcast foi cunhado. E eles ainda estão enviando gravações!
Ao pesquisar isso, encontrei alguns vice-campeões:
Todos esses podcasts terminaram desde então, mas Todos os jogos considerados foi a mais longa delas, terminando em agosto. 02, 2018.
Outro que surgiu foi Podcast da Mesa-Redonda do Macaco Harping, mas a data do primeiro episódio que pude encontrar foi 14 Episode em dez 02, 2005. Sendo assim, acho improvável que o Episódio 1 tenha sido anterior ao lançamento do XNPG em RPGMP3.com.
Curiosamente, não foi até a 2007 que "Melhor Podcast" se tornou uma categoria de prêmio nos Ennies (foi para Tenha jogos, viajará).