Before we can really answer your question:
In what manner of efficiency do you want?
Would placing all lines in an array and picking a random number based on the size work or too memory intensive?
Would checking the size of the file with "wc -l" and then reading down a random number of lines work? Or is that not portable enough?
You could read the file twice to avoid the "wc -l" which is a bit intensive, but the filesytem may give you leeway with buffering.
You could massage the data so that the leading line has the # to go off of. Or even better create a file with the size data in the first block you read and then seek to the random spot.
If none of this gives a clue for you to go off of, then please give more info back.