I think you didn't have "rythm" as technique.
You still think rythm as "backing" to your solos.
But it's not!
Actually ,the rythm guitar is the song structure ,and Solos are the icing.
If you want to be more creative ,you have to begin with rythm first ,than write the solos on it!
Well.
1)For rythm playing ,the picking hand is more important one.
2)Rythm is first in your head. Learned legato runs can't save your butt here
3)If you can arpeggiate any chord (I know you can) ,there is a strong possibility that you can write great rythm tracks without chords.
4)Palm muting is your best friend.Your second best friend is changing the picking position Vertically and horizontally ,the 3. best friend is a metronome!!!
5)Turn your "gain" back a bit ,and try to feel the punch and chunck ,instead of "lead" structure.Since rythm begins with "hitts"..Tone is the second part od the picture.But you have to get the "hit" part first.
6)Play with a drummer for hours.At the point you and him have great time (With playing music ofcourse) ,you will be good at rythm ,and he will be a master LOL
7)Everything above is my humble opinion ,and I can assure you that I am more a rythm player ,and a drummer.