Macroscopic fossils, fossils big enough to be seen with the naked eye, appear in the late precambrian, and they come in a surprising variety, but if the Phactor remembers correctly, and with a check in the literature indicates he does, actually the oldest macroscopic fossil is a seaweed similar to red algae that dates to 2.1 billion years ago, not some 600 million years ago. Now this was not actually very spectacular at only about 2 cm tall, and since red algae are basically filamentous, it makes sense that they were among the first large organisms. Even at such a size, such a tiny seaweed would tower over a microbial mat community like a redwood towers over a moss. So actually life got bigger a lot eariler than many people suggest. This was the second of two big episodes of size increase in the history of life, the first being when eukaryotic organisms appeared allowing cells to be considerably larger than prokaryotic cells. Multicellularity allowed organisms to be even larger resulting ultimately in blue whales and redwoods.