Traditionally a lot of the issues with large animals comes form getting them in and out of places to actually be used. Dungeons with 5' doorways and corridors, stairs/ladders and so forth. It's mostly a logistical problem. A medium sized mount or one that can fly tends to solve some of those issues.
Now an Eidolon doesn't deal with a lot of those problems. It's intelligent and you can summon it into places easily enough if not in combat or pressed for time. That allows it to be less stressed by those logistics.
A themed unicorn mount Eidolon should work just fine. Remember however not to focus on it completely, your summoner is a large part of the build. You can easily turn a lot of problems into solutions. A small summoner on a medium mount with a few mounted combat feats is just as scary as most other things on a mount. They can wear armor, they have d8 hit dice. It's entirely possible to build the summoner to be the combat monster and let the eidolon be the support like that especially with the right traits and feats.
You don't even need to do small if you can just be patient.