Ordering by newid() is pretty lackluster in the performance department, I assumed this article would cover some great new ways to randomize data 🙁
I've gotten by in a variety of cases by using row_number() over some indexed column(s), and predicating to some random offsets. This ends up being significantly better than the newid() approach, but the perf is still not that great if you have huge tables and some of your random offsets are deep into the table.
The other main approach I've seen is using tablesample (i.e. http://www.mssqltips.com/tip.asp?tip=1308), this may work better on very large tables.
For the common variety of requirement of fetching some random images in a website image gallery, I ended up creating a table to contain a randomized list of keys to the data rows. So if each image has an identity column as the PK, the randomized table contains a list of these ids in random order. You pay the perf to order by newid() one time with a nightly job, then each request simply chooses a random entry point into the randomized table and queries out the next N ids. Since the randomized table has contiguous ids it is cheap to seek into - where id is rand between 1 and max(id).