Yea, I thought about that, but he doesn't mean theta, either. What he's giving is a physical impossibility proof -- you can't do memory access better than sqrt(N). When he gives a physical example of a machine of arbitrary size that accesses memory in sqrt(N) time, then we can talk about theta.
The speed of light limitation on distance to DRAM memory is real, but so far seems to affect mostly supercomputers. Are there any large server boards where speed of light lag is the limit on memory capacity?
I wonder if this is what one interviewer was trying to get at when he asked me over and over again if a binary search was worst case O(log N). I just kept saying that if you took more than log N steps to perform a binary search then you by definition did not perform a binary search. He was off his rocker so I kind of doubt he was looking for the difference between little-o, theta, and big-O. It's good stuff to remember and might impress a more sane interviewer some day though.
That's why everyone writes that comparison sorts are O(n lg N), even though it's also technically O(exp N) as well.