Well I have Suddenlink Cable and my download speed is 15mb down and I was able to do the Lion Recovery Download in 30 minutes. Then the Lion install took another 20 minutes total time was little less than an hour.
Personally I wanted to try out the Internet Lion Recovery to see exactly how it worked. I think it works great, but of course it would all depend on ones internet service because if all you have is a 1.5mb download it would take a pretty long time, so doing it the clone route would be the smart way to go.
Oh one thing I will share is that I took the SSD drive from my old mac mini and initially all I got was a flashing circle with a line through it. I actually had to put my SSD drive in my other Mac, repartition the drive and leave it raw. It was then that the Internet Recovery actually came up automatically. If you are using a new drive then it will be raw by default.