For flavour, I recommend that all “regular” animals that normally have sharp-pointed ears now have human-shaped round ones.

Inspired by MTG I'd say a Displacer Kitten. Basically a house cat sized version of a Displacer Beast, either naturally young or kept young with magic. All the cuteness of a kitty with the deadliness of a Displacer Beast

Fey creatures in general. High level fey are where things start to get tricky though. Pixies that are police for instance, obsessed with checking peoples' papers. Or how about gnomish pacifists. Hags are also fey, so an easy addition, I'd perhaps go with them as the potential allies - they are usually unaligned and wouldn't want to side with elves or a kingdom

In some settings bulettes hate the taste of elves, and maybe that could allow militaristic elves to domesticate them for use as raiding mounts. I'm imagining an elven archer atop a saddle with a bulette-hide shield along the dorsal fin. The shield is sturdy enough that it allows the rider to duck down and be protected while the mount tunnels, as well as providing cover when shooting their bows. I think this could work well for a single scout ambush encounter at level 5+, and as a special siege unit that the party has to defeat later on.

Maybe they learn about it from a group of wounded soldiers recounting a recent battle where a castle wall collapsed without warning, and in the chaos three mounted land sharks tore through their ranks until they were ordered to retreat.

Check out the Fomorians or Nothics, could treat those as a company of the enemy elves tried controlling dark magic for the war effort and were corrupted by it.