Burst Angel - Meg and Jo
Hellsing - Alucard and Integra, or Alucard and Victoria Seras
Adventures of Mini-Goddess - There's an episode where the air conditioner malfunctions and turns the room into a snowy landscape, and Gan-chan (the rat) has to help them out...
Samurai Champloo - Jin, Mugen and Fuu
Grenadier - Rushuna, Yajiro and Mikan
Scrapped Princess - Pacifica, Shannon and Raquel
Le Chevalier D'Eon - When D'Eon is his sister Lia, there are quite a few scenes with her and the three companions
Revolutionary Girl Utena - Utena and Anthy
Kiki's Delivery Service - Kiki and Jiji
Laputa: Castle in the Sky - Sheeta and Pazu
Excel Saga - Excel and Hyatt (or Excel and Menchi, if you wanted to stretch it a bit)
...I'm sure I'll come up with more after I think about it for a bit.

Did you only want a heroine, or will a male main character and a sidekick do as well?
Edit: How about
Cowboy Bebop - Ed and Ein?