Probable correction: "In the South I am known as Incanus, to the East I go not" - the South doesn't refer to the the Southrons/Haradrim. I'm sure in one of the Apocrypha (you know what I mean! Probably UT.) it says that in this context the South means Gondor. He is known to have spent a lot of time there (when he was still welcome, anyway), whereas there is no evidence he went any further South. Unlike Aragorn, of whom I believe it is stated that he went as far as Harad.
Gwaihir, the Windlord, speaks to G in both TH & LOTR, if memory serves. You've also left out one of Gandalf's soubriquets, Grayhame.
Is it possible to have 'will' without 'intelligence'? I've always regarded Shelob as both intelligent & malevolent, but she certainly doesn't speak in LOTR (unlike the spiders in TH). Her origin is a bit mysterious. I seem to remember she's a descendant of Ungoliant (equally mysterious) rather than a spirit in her own right.
I'm fairly sure one of the talking Ravens of the North is referred to at some point in LOTR. To be certain, I'd have to and look it up, but isn't Carc the raven in TH, & Roac, son of Carc mentioned in LOTR?
The only other possibilities for Dave's animal I can think of off the top of my head are Bill the pony, Shadowfax, or the thrush that fetches the raven in TH, but none of those fit his question adequately.