The group is Cretaceous, outside Neornithes, and a good rounded reference point for early records is about 90 million years ago.
What makes hesperornithiform birds so interesting is that they show just how experimental early bird evolution already was in the Cretaceous: these were not vague “almost birds,” but highly specialized diving birds, many of them flightless, living outside modern crown birds and already adapted to a fully aquatic lifestyle about 90 million years ago. They reveal that long before the modern bird world took shape, evolution had already produced powerful foot-propelled swimmers that filled marine and freshwater niches in ways that echo loons and grebes today, while still belonging to an extinct branch of the avian story.
They were not penguins, and not close penguin relatives either. Hesperornithiformes were an older, separate branch of aquatic birds that evolved similar features because they lived a similar lifestyle, a classic case of convergent evolution rather than close ancestry. They disappeared in the Cretaceous–Paleogene extinction event about 66 million years ago, the same catastrophe that wiped out the non-avian dinosaurs and many other bird lineages outside crown birds. So the short version is: they were successful diving birds for millions of years, but their branch died out at the end of the Cretaceous, while the line that led to modern birds survived and later produced very different diving birds, including penguins.