I like the rabbit and the frog ideas as they're easiest to immediately connect to the animals running them (and seeing a rabbit in a maitre D un outfit would be the best thing ever).
Also, the potential inn/tavern names are just friggin' awesome.
Frogs:
The Hop and Holster
The Leg-mad Sous chef
The Croak and Wart
Tadpole's Rest
Rabbits:
The Hop and Holster (they both hop!)
The Flayrah (gotta have some watership down reference in there)
Carrot and Clover
The Eagle's Folly
The Owl's Head (Like, they killed an owl and mounted it's head over the fireplace)
The Warm Warren
There's so many optioooooooons!