I have always liked military-style names for male horses: Brigadier, Trooper, Scout, Soldier, General, etc. Funny how my male equids have not had any of these names! (Goose, Blackjack, Tom Terrific and Dusty. Dusty would have been Brigadier or Trooper if he hadn't already had his own name for 11 years...)
For females, not so sure. I had a paint pony mule I called Sassafras, or Sassy for short. I liked that a lot, especially since her coat was mostly the reddish-brown sassafras color.