I'm at "Soft-Hearted Devil" with the Legion. I've killed everybody in the Fort and Cottonwood, including Caesar. The fame does not seem to go down any further. I want the Legion Assassin groups to show up.

How can I lower my fame with the Legion further?

I think liberating Nelson and resolving Boones companions quest (has to trigger first) at Bittersprings will get you Legion Infamy. But with wiping out both major camps you already did the big jobs.

Killing Caesar should've netted you the lowest rank, it's odd that it didn't

Come to think of it: have you done any quests previously that gave you Legion Fame, i.e. pro-Legion quests? That might be an explanation. Or something bugged out.