First of all, Nadal is the best clay courter ever. So you're going to have a hard time finding someone who could challenge him realistically anyway. Ferrero was extremely fit in his time, amazing speed also, but those are all things Nadal also has and is just better at. Coria was a briljant player, but nowhere near physically strong enough to challenge Nadal. Kuerten is interesting because he had this aggressive style of play on the clay which was quite unique. I just don't see him as the player who could hang with Nadal all the time. Gaudio is special. I consider him the most talented of the lot, but also by far the most brain dead. I always found the Monte Carlo match of 2005 against Nadal very telling. He played great in the first set, displaying some great tactics to use against Nadal, only to go completely away mentally after that. Gaudio would be my pick to take a set of Nadal, but in the end he is always going to lose.
I do feel you're not getting the facts straight about Coria though. To say his prime was 2003-2005 is not true, I believe. In 2003 he was still very young and green. He was still only 21, not everyone is like Nadal already winning slams at 18. He was good enough to rap up the smaller clay court tournaments (Won Buenos Aires, Hamburg, Stuttgart, Kitzbuhel and Sopot), but not physically strong enough for the big tournaments. You're now probably saying Hamburg is a big tournament. Which is true, but even in that tournament you had the high drama match against Gaudio in which he was physically hurting. I don't believe he was physically strong enough to win Roland Garros. He had a gruelling 5 setter against Zabaleta (4+ hours), 4 sets against Agassi before he lost to Verkerk. Nobody looks good losing to Verkerk, but it's a bit stupid to give that as a reason why he can't challenge Nadal.
Also in 2003 there is no such thing as him winning only 6 games against Ferrero at Monte Carlo. He lost the final 6-2 6-2. The match was shortend to a best of three setter because of the cold and wet conditions. Coria couldn't hold serve to save his life, he lost convincingly.
And to say Coria never dominated like Nadal is true, but he did came close in 2004. He was 22-1 going in to that Roland Garros final. He was the favourite to win it and only lost one set prior to the final. If he won that we would look at it very different.
Coria in 2005 was not as good as in 2004. He had an injury at the end of 2004 and it wasn't untill Monte Carlo in 2005 untill he had a good result again. I think he was already happy he was in a final again. In Rome he showed glimpses of his old form, but he was too irregular. The match against Nadal there was some prestige involved as Coria wanted to show he was the better clay courter. There were patches of good play, with some great tactics to use against Nadal from which anybody can learn really, but he wasn't consistent enough to win. Played horrible in RG to lose to Davydenko. The Coria of 2005 was but a shadow of 2004. He showed glimpses of his form in Rome, but that was it. The only time he played really well was during the US open in 2005, but that wasn't really his surface.
What's a real pitty in my eyes is that Gaudio never played Nadal at RG in 2005 because he lost to Ferrer. I'm not saying he would have won, I just really wanted to see that match