Improving search requires adding more and yet more attributes to pages. The search problem then becomes one of allowing search over the set of all page attributes without presenting a huge text menu. Even if a text menu is used it should be adaptable to the user's searches so that even if it's horrible to use at first, it reorganizes itself over time to better serve the user. One problem with this might be that the user becomes lost in an ever-changing menu. This might not be so bad though with icons to represent the different attributes and reorganization of attributes by regrouping the icons in a two-dimensional or three-dimensional space (separate from the space of page icons). Here are some ways to do that.
 
A Timeline

A user-selectable timeline slider with exponentially decreasing accuracy into the distant past: as the user approaches the present, the timeline becomes more and more fine-grained until it's down to seconds to the present. As the slider is moved, different parts of the space light up indicating that they were added at that time.
 
A Radar Screen

Pages light up as if they were phosphors on a radar screen then they decay away. That reduces the clutter and human spatial memory might be better exploited to aid search.
 
A Monopoly Game

A monopoly-like game board with labeled categories going around the board. The user can search by clicking on a category then drilling down the subcategories within that category. There is also a general purpose unlabeled category in the center of the board that the user can put different found pages in to make a new category. Each of the categories are colored differently and items between two adjacent categories have an intermediate color.
 
A Blob

Each category is produced by the system itself by searching on the web (or within the user's local pages) and each blob displays the things it contains in sequence. When the user clicks on a blob it splashes as if it were a blob of mercury and scatters into a spatial arrangement of the things it contains. The user then clicks on various of those things to view them.

Alternately, instead of simply displaying search results the system could take the user on a guided tour of the found pages as if the user is in a taxi. The user then has the chance to get off the taxi at whatever stops seem interesting.
 
A River

Categories of data could be represented as rivers of information. The rivers can be labeled or they might be remembered simply by their shape. If the user does nothing at all the rivers flow by like a ticker tape (except that they have sinuous shapes instead of simple straight line edges).

The user can select various pages flowing past in the river and put copies of them on a bank of the river, thereby forming a cluster of information and making that information easier to find again (rather than watching the river until it flows by again). That cluster of information might be the same sort of thing as static arrangements of pages like the information city idea, so the river idea can be both dynamic and static at the same time.

The user could create new rivers by selecting items flowing past from different rivers and asking the system for a new river made only of things that share the same attributes that the selected pages share. That new river might then be named (and even shaped) so that it's distinctive.

A user might take a river and apply a filter to it to generate a new river (a new category). This means that boolean searches can be made entirely visual. Many people have a lot of trouble understanding boolean searches.
 
Assisted Gravity

There is a ring that the user can drag different pages into. The pages dragged into the ring serve as examples of what the system is supposed to search for.

The ring serves as a magnet of pages similar to the pages put into the ring. Clicking on a particular page activates that page's gravity (or magentism). Pages that the system judges to be similar to the selected page drift toward the ring.

Once the search is over the system could put the resulting pages inside the ring. The ring is featureless at first but as the user drags in pages the ring becomes a ring of those pages. When the search is complete the found pages can be arranged inside the ring so that each one is closest to the ring pages that it's most similar to and furthest from the ring pages that it's most dissimilar to.

More generally, as the user throws things into the ring to begin a search the system analyzes them to find the centroid of those pages and page clusters. Then it moves the pages around within the search space to show the user what it thinks is the most relevant set of pages. This tells the user what the system thinks the user thinks is the appropriate set of attributes to search for.

Once the user clicks on the ring to initiate the search the system moves pages toward the ring with a speed proportional to the degree of similarity the system detects between the page and the centroid.

As the pages and page clusters drift toward the ring the user can move them toward the ring or away from the ring. Moving a page away from the ring indicates to the system that this particular page should be used as a counterexample of what is being searched for. The system then modifies the speed of pages moving toward the ring based on this counterexample.

Similarly, moving a page toward the ring as the search progresses tells the system that this page is close to what the user is actually looking for. That also should be interpreted by the system as an example and therefore another indicator of the various speeds each page is moving at.

Of course the user should have control of the overall speed, else things might crawl too slowly or zip along too fast. Adding animation to searches should increase the game-like feeling of the system.
 
Category Space

The user dynamically creates arbitrary categories each of which the user gets a chance to either label or attach a graphic to (the graphic serves as a reminder of what the category is without needing a text label).

Past categories then appear in a space of categories, separate from the space of pages. The user can select various categories and put them in other categories so that later searches can start with the atomic categories or with the molecular categories. This lets the user group categories into more reasonable sets of categories, which makes organization easier. Note that a single page or category can belong to multiple categories.

The user should be allowed to edit this space at any time to split categories that have grown too large, or to merge categories that are too small, or to rename a category, or to move categories around inside the space.

The categories that exist at any one time indicate to the system the user's interest areas. Each category in category space is then an interest area the user has already taught the system to recognize. As the user uses the system, new categories might be suggested and, if the user approves, added to category space.

Note that a growing and differentiating category space presents visual confirmation to the user that the system is learning new things about the user all the time. This should aid the feeling that the user is making progress toward some ultimate goal and therefore increase the game-like feeling of using the system.