You can download the most recent (hopefully*) unbiased sample of YouTube videos here or you can read how it was made and why.
Right now, the sample includes 359,812 different YouTube videos that were uploaded mostly in April and May 2009. The file's format is CSV. First column is the URL (http://www.youtube.com/watch?v=EHlH0yWVKR4), second column is the time of upload (2009-04-28T19:47:42.000Z) and the third column is length in seconds (256). The files are sorted alphabetically by URL. The current file's size is 25.3 MB.
* Why "hopefully"? Some undetermined kind of sampling is used on YouTube's side. See bellow.
While researching for my thesis, I found out that there is no simple way to get a random sample of YouTube videos. The page Recent Videos shows only 1,000 of them, which accounts for only a small portion of that day. Research using such a sample would be biased.
I found out that at least one other researcher had the same problem. Michael Wesch (whose video you might know) got his nearly random sample with the following method: "Every 2 hours, one of 8 researchers loaded the 'Most Recent' videos on YouTube and analyzed the first 20 videos (the most recently added at that moment). This was done to eliminate the sampling bias of different times." This, of course, is pretty hard to do over long periods of time. Michael Wesch chose to do this for only 1 day. Still, his YouTube Statistics research corresponds quite accurately with what I found out, so it couldn't have been that biased.
For my thesis, I chose almost the same method as Michael Wesch, but automated it.