If the Alien universe lacks FTL, and all the Engineers have is routine relativistic space travel, it might be plausible that their shape and form stood the same for billions of years - the people returning from their travels even thousands of years later would help keep change constrained. For this to be plausible, space travel would have to be about as common as flying on vacation is for us, but that may very well be the case for the Engineers. Indeed, the much younger human Nostromo is clearly a "space truck", effortlessly making multiple-year long journeys just to ship "oil". Shipping oil over interstellar distances using chemical rockets would be ridiculous, so it's safe to assume their engines are far better than anything we have now.
But we still know very little about the mechanics of the Alien universe. Do they have relativistic space travel? Do they have FTL? Could it be that the relative easy of travel for the Nostromo is a result of an FTL drive the Engineers never developed?
We have little evidence on the age of the Engineers' species. Prometheus suggests that they at least influenced human development on Earth for several thousands of years which at leasts provides a rough lower limit, but that would still be a far cry from the billions you suggest. Some suggest the Engineers originally seeded the Earth with life, but that's not supported by the introductory scene in Prometheus - we can see that there's already a oxygenated atmosphere there, as well as some plantlife. What about the Pilot? There's a few things we need to note - first, fossilization doesn't take billions of years; depending on the environment, it might take a very short time, or it might never happen at all. It doesn't prevent all damage, and the ship itself shows few signs of decay, despite being on what seems to be a world with an atmosphere. It also doesn't seem to be covered in any visible amounts of debris.
Fossilization is a relatively rare event on Earth, requiring rather special conditions - it's doubtful it would happen in an isolated spaceship on a lifeless world. It isn't just the decay of everything but the bones - it needs a source for the minerals that "replace" the now vacant volume of the body; on Earth, fossils are created when those minerals precipitate out of mineralized ground water. The Engineer wasn't exactly burried in well-watered ground. We also know the Xenomorph eggs survived in a viable state, despite being in the spaceship for just as long; you could say that the cargo bay was in stasis, but that would still require the containment to hold for "billions of years", suggesting it's independent of the ships systems, requiring no power or maintenance. Not outright impossible, but quite a stretch. Ultimately, the one who said the Engineer was fossilized was Dallas, a space trucker. He had scarcely any time to do a real examination, and just recorded his first impressions - Prometheus clearly shows that what Dallas was actually studying was really the suit and flightchair of the Pilot, not his body.
There's no such thing as "genetic perfection". Evolution is no progression from lower life forms to higher life forms, with some final state that would be unsurpassable. However, as I already outlined, there are some arguments that can be made to show the genetic drift in the Engineers might be minimal. It's also quite possible, given their apparent capabilities, that they "breed themselves" in a way that stops the change, or that they have frozen their own genetics to stop evolution from proceeding at all. It's not entirely clear why they would do such a thing, but it's something that can be deeply cultural, with their own idea of what perfection is, and striving to keep their already perfect form (as far as they care). Again, for interstellar travellers, this might be desirable - it would prevent speciation in more isolated reaches of their influence, which might cause conflict over "who's the real Engineer" - perhaps similar to how "white" Europeans have considered "black" Africans inferior, despite the fact that the same Europeans have ultimately descended from the ancestors of those their contemporary Africans. Now imagine the same thing on a galactic scale, possibly with not just racial diversity but also what would then be an entirely different species, with just a common ancestor.
Out of universe, while an earlier script of Prometheus assumed the events take place on the same moon as Alien (and thus, the Engineer we see in Prometheus would be the same dead engineer in a crashed spaceship in Alien), this has been subsequently changed. An earlier script of Alien suggested the ship crash/landed around ten million years before the events of the movies, with the Xenomorph eggs in stasis.