Brent Ozar shares four methods for getting a random row from a table:
Method 1, Bad: ORDER BY NEWID()
Easy to write, but it performs like hot, hot garbage because it scans the entire clustered index, calculating NEWID() on every row:
That took 6 seconds on my machine, going parallel across multiple threads, using tens of seconds of CPU for all that computing and sorting. (And the Users table isn’t even 1GB.)
Click through for the other three methods. The really tricky part is when you want to get a random sample from the table, as TABLESAMPLE is an awful choice for that.