[Beanamir of Gondor]

One person I sorely missed was Sharku, because we totally lost the Scouring of the Shire without him. Along the same lines, we had the tiny little Sackville-Baggins cameos that could have been made into a lot more.

I would also include Beregond (because we've been barred from missing Faramir :P) because he represented part of the Guard of the Citadel that didn't either
(a) blindly follow Gandalf after he beat up Denethor, or
(b) blindly follow Denethor's orders after he went mad.
I think Pippin's love of Faramir was a very poor substitute for Beregond's, and if we had Bergil as well, his relationship with Pippin would have been hilarious and adorable.

Finduilas already mentioned Dernhelm but I'll mention him again. I was so incredibly disappointed at the Mustering of the Rohirrim. The scene was fabulous (Merry dejectedly watches everyone leave, then suddenly a hand scoops him up and puts him in the saddle) until Eowyn revealed herself. In the book, Eowyn became a really heroic and noble figure by not revealing herself until the Witch-King appeared. In the movie, it's kind of like... "Well, now Merry knows precisely who you are, and the two of you can snivel and be scared together before you fight on the Pelennor." Both of the characters lost some bit of courage, knowingly being together.
Plus in the EE there's a section where the two of them sit around and eat with their helmets off. Where the heck was Eomer?