Just thought I would create this for anyone who doubts that it can be done. A list of most US cities and the state they are in (I can think of a few jokes here...). Over 59,000 items.

http://www.wssdemo.com/Lists/Large/

The state field is just a text field rather than a look up (because the source was an Excel file). The default view is grouped by State with an item limit of 100 per page.

Performance was pretty good without adding an index to the State field. After turning on the index I think it generates the page a little faster.

The nice thing about the Group By view is that it uses Ajax like functionality. This is where the index on the State field improved the performance of bringing back the cities very quickly.

From this list I plan to build some other demos that use this as lookup data.