Mine are based on before the Fellowship hits Lorien, since they all basically look the same cloak-wise afterwards:
Aragorn: a dark green-black one would be best; it would be even better if TLG had modeled the Weathertop minifigure after his Strider outfit, but nothing that can be changed there.
Legolas: whatever he wore in the 1st movie (brown?)
Eomer: the green cloak looks good on him, but for movie accuracy the minifigure should've been bare-backed.
Pippin: I don't mind the one that came with him, since red would've clashed a little with the outfit.
Gimli: dark blue.