The coolest way to name your companions I’ve seen is to make jokes to your teammates, guild master or in my case, the game developers (combine the first 3 letters of the names to get FunCom).
It’s also nice to name your companion by your name so that clan members can take you to the dungeons when you’re offline 
I usually name animals after common objects:
- Hammer (rhinoceros) ; Funnel (dog) ; Carpet (tiger).
When it comes to humans, I give them longer names, such as:
- Ferdinand the Frightened ; Exiled Jack ; Bald Helena.