Methods For Handling Large Datasets

Lets say you want to offer users access to a table that has over 1,000,000 records in it.  You dont want to fetch the entire table into a dataset.  Even with paging, it will still cause a performance lag, will it not ?
Lets say there was a column that held last names.  You could then divide up all the data in to alphabetical groups by letter.  That will at least let you split up the data 26 different ways (letters in teh alphabet).   Thats still roughly 38,000 possible records in the dataset at any given time.
 I suppose since the database and web server are very close to each other, physically, the latency shouldnt be too bad.  However, Im worried about having several dozen or more users, each requesting datasets with tens of thousands of records.  That would cause the memory use on the web server to spike most likely. 
 Right now, its just one user do this sort of processing, but that might grow to include several dozens.

ideas ?