Hmm, one of the guide dog breeders my old boss knew had named a series of litters with Tolkien influenced names. I personally liked Beren and Strider as doggie names. Strider is probably best suited to a leggy breed such as a Weimeraner or German Pointer. Beren maybe for a sturdy dog such as a Mastiff or Boxer.
Smeagol might be sweet for a tiny wee Pug, and Tulkas for a tenacious Border Terrier.
If I get another cat though, it's getting named Ozzy, even if its a girl - not that you can tell with a cat until its too late, hence the gender-confused Lemmy.