The two distinct issues here that most folks seem to agree upon are:
PROBLEM #1: siege frigates have been nerfed to the point of complete redundancy
(thanks innociv for your comparison with marzas)
Potential Solutions:
Nreth: reduce siege frigate supply, make planets stronger
- downside : buffing planets unbalances capships vs planets
- planets are already pretty tedious to kill
Snipafist: completely change the role of siege frigates from anti-planet to anti-heavy, modify roles of other ships accordingly.
- downside : this sounds like massive work rebalancing the entire game
TarlSS : nerf lrm anti-building damage, buff siege frig anti-building damage
- downside : static defenses are no longer any use at combating siege frigs
innociv : revert siege frig costs to 1.02 levels, keep supply & survivability nerfs but significantly increase anti-planet damage
- i quite like this idea. A significant damage increase - perhaps coupled with an increased reduction in survivability & cost. Siege frigates would again be useful in leveling enemy planets after achieving orbital superiority
- making hit and run flanking attacks with siege packs against poorly defended planets would become a viable tactic, adding more depth to the game
- maybe siege frigates could be made a bit slower as well so they could be hunted down fairly easily if unsupported
PROBLEM #2: less experienced players have difficulty combating the AIs beloved siege frigate pack tactic
The two obvious ways to address this that have been pointed out already are
i) nerf siege frigates
ii) reduce the AI's love for building siege frigate packs
Clearly the former approach hasn't worked. I have a few opinions about the latter idea:
a) Patching the AI so that it makes poorer strategic & tactical decisions on Hard & Unfair modes is an awful idea. Note that I'm not implying that the AI's use of siege frigates is currently a good idea.

MegaVolt makes the excellent point that patching the AI so that it relies less on siege frigates may actually make it harder to beat, considering how useless siege frigates are / have been.
c) My suggestion - why not just patch the AI so it doesn't use "uncounterable"* tactics like siege frigate packs when in Easy & Normal mode? Less experienced players who have not yet learned how to combat these strategies can have fun in the lower difficulties, and people looking for more of a challenge in single player can play against the harder difficulty levels of AI.
Finally, playing the devil's advocate, here is a somewhat tongue-in-cheek suggestion which addresses both problems : the redundancy of siege frigates & the problem less experienced players have in combating the AIs use of them:
Since siege frigates are redundant in competitive play, why not just cut them from the game completely?
* : note sarcasm