If the DM trusts you as a player, and your game takes story aspects seriously (things like NPC reactions to wild animals, the ins and outs of stabling animals within cities etc.) there's no reason not to let you just find a creature you are interested in having be your animal companion.
You will know based upon where your character is what the likelihood of different beasts are out there to find. If you and the DM takes the world seriously, you both know you won't be able to just go out and "find a T-Rex" or "find a Winter Wolf" or "find an orca" or any of the odd/or and overpowered choices... you will have to make realistic searches for what animals you might come across. And truth be told... if you did happen to lose your original companion... you might very well end up finding a new one based upon the adventures you have and who you come across as part of the story, rather than just doing the lame thing of flipping through the Monster Manual and finding the biggest and baddest beast there is and pointing at it, declaring "This is the one I want!"
The Beastmaster subclass and its animal companion is as much Story as it is just additional PC combat power. And if the DM believes you will treat your choices in that way... as an extension of your character's growth... then it won't matter what type of animal it is if you are more interested in playing the relationship between you and it, rather than just using it as another random damaging attack.