I'm surprised no one's mentioned PB Blaster, widely available in hardware stores and Home Depot for around $3-5 a can. I can't speak to its safety on blueing or case coloring, but its effectiveness for other things, large and small, has been remarkable. Numerous times over the years I've used it to loosen threaded tie-rod ends on steering racks, a process that previously required heating the tie-rod end with an acetylene torch to break the rust and crust inside the threads. With PB, I'd spray the joints a few hours before removal and off they'd turn with a big Crescent wrench. And those tie-rod ends only had two flats for turning, not hex heads.
