Answer: Larry's first patent

Sorry about the delay in answering..  As I was writing up the answer, I noticed a bug and needed to let some folks know about it.  

But back to our problem--what was Larry Page's first patent?  

As Aleatha correctly points out, Google has a very nice Patents property.  (Just as Google has News, Images, Video, Scholar... so too we have a collection of US Patents.)  

However, it seems that the Advanced Search function on Patents is currently not working correctly.  Because my answer WOULD have been, SHOULD have been:  Use Google Patents, use the Advanced Search interface and search for inventor "Lawrence Page" (because people typically use the full form of their name, rather than the diminutive).  

Alas, that's the bug.... At the moment, it seems broken.  (It will be fixed soon, I hope!) 

But what does it mean to be a skilled searcher if you can't work your way around it?  

So, using just the regular Google Patent search page, you can enter [ Lawrence Page ] and sort by date.  That's not hard, but it is a bit painful to sift through all of the non-Google-related patents.  You could even try quoting his name,  "Lawrence Page" but even that won't help much.  

Another approach (and what I actually did) would be to go directly to the US Patent Office web site (USPTO.gov) and use their advanced search UI.  Note that their's is a bit more baroque than Google's (for instance, you have to do the search [ IN/Lawrence AND IN/Page ] in their system).  The good property of searching the USPTO is that you'll find only 12 hits on "Lawrence Page," so it's simple to figure out which one was first. 

From USPTO, then, the answer is US Patent: 6,285,999  granted on September 21, 2001.  "Method for node ranking in a linked database."  

(And I'll see if I can't get someone to fix that bug in the Google Patent property...)