When I'd first played these games, I had no idea what Pokémon these fossils would wind up turning into, so I couldn't make any exact decision; I chose randomly by going eeny, meeny, miny, moe.
Though, my most favorite Pokémon of these fossils would likely have to be Kabuto. It evolves into Kabutops, which is one of my most favorite rock-types of all time. Although it can't perform too well in terms of competitive battling and whatnot due to its low amount of stats, sadly, it's still perfectly usable in-game. Have tried it plenty of times on my FireRed team, and it has never failed me.
Alongside above, it's also got a pretty unique look; none other Pokémon seem to actually share it. I suppose it could be argued that Scyther is a little similar, but not completely. Have always been wanting to see Kabutops gain an actual evolution in future, but I'm not sure what the chances are of it happening. Though, if it doesn't wind up getting any evolution, it'll likely be getting a mega.
As far as Omastar and Omanyte go, they're my favorite as well, but are also a little more down on the list.