Fractals provide not only the illusion of detail, but the ability to explore that detail into infinity at very little storage and process cost. It would be additionally appropriate with simulating gardens, since fractals occur everywhere in nature.
As for storing thousands and thousands of randomly generated objects, look into seeding. Sometimes the right algorithm can boil down an entire universe into a single integer.
http://www.gamasutra.com/view/feature/3377/algorithms_for_an_infinite_universe.phpRegenerating the universe each play time might get costly eventually, but load times are always a problem.
As for storing a players changes to a large world, well that depends on what s/he's changing. There's likely no other way of doing it than to just log the actions of the player and pushing it through when the game reloads.
And you might have to resort to 2D for large worlds, at least initially. Check out what this guy is up to if you want to look at performance of a large generated world:
http://www.infinity-universe.com/Infinity/index.php?option=com_frontpage&Itemid=26This especially:
http://www.infinity-universe.com/Infinity/index.php?option=com_content&task=view&id=106&Itemid=27
