Order by GUID vs Skip(Random(0, Count)) performance for random entry

Just wondering about some performance question for accessing random entries in SQL Server with Entity Framework.

The common solution recommended in many places I've found is to use

db.Table.OrderBy(x => Guid.NewGuid()).FirstOrDefault()

What I'm wondering about is if it would be more efficient to instead use

var skip = random.Next(0, db.Table.Count());
db.Table.OrderBy(x => x.Id).Skip(skip).FirstOrDefault()

Since the first alternative relies reordering every entry in the table randomly (unless SQL Server has some special optimization for this?) while the second should retrieve the number of items (which I believe runs in constant time) and then only retrieving a single element.