What is the oldest fossil on Earth?
The oldest undisputed fossil are Stromatolites, bacterial mats, the oldest of which are dated ay 3.7 billion years ago. The key term here is undisputed, there are other possible fossils but it is very hard to have certainty with chemical or cellular fossils. The oldest uncertain fossils trace back to 4.28 billion years and are possible bacteria trapped in hydrothermal vent products.  

The oldest fossil of a creature with a brain is weird. it is actually several creatures from Ediacaran biota. These are also some of the oldest multicellular life fossils, lacking any hard parts fossilization of early small animals is incredibly rare event even considering how rare fossilization already is. There are several bilaterally symmetrical animals capable of movement, this combined with the fact they are more than two cells thick means they almost certainly had a brain.

Kimberella and Spriggina and their relatives are both almost certainly mobile, with some form of nervous system based on phylogenetic bracketing, others are also likely since the ancestor of chordates may in there somewhere. We know there were moving creatures from the ediacara because we actually have trace fossils that are consistent with a muscular moving organism like anemone.