There doesn't need to be any particular reason why they were originally classified by even- vs odd-toed

The more interesting question is why did this classification held up? Why wouldn't the number of toes change, or why would it remain odd or even when it does? It really seems that it's such a random criterion that it should have been blown up by molecular phylogeny by now

I honestly don't know the answer, but it may have to do with the fact that all odd-toed ungulates will tend to have most of the load on their central digit, whereas even-toed ungulates have two central digits that they load more or less symmetrically. in turn that completely changes how the ankle is loaded. To go from one system to the other you need to change the whole alignment and mechanics of the leg, and that could be something evolution can't easily mess with

as for how weird orcas/cetaceans are compared to the rest... evolution isn't always stable. as they adapted to life in water a lot of things have obviously been tuned. though seeing how cetacea are related to hippos we at least understand how they might have spent time in the water in the first place. same thing goes for tetrapods, they're definitely very abnormal fish. some salamanders could pass as fish if you remove the legs, the rest not so much