Aren't they both illegal regardless of severity?
Like Muggle prosecutors, the Ministry of Magic can decide whether or not they will pursue charges in the interest of justice.
...[H]e blew up his aunt, for Gods sake!' Fudge shouted, banging his fist on the judge's bench and upsetting a bottle of ink. 'And you very kindly did not press charges on that occasion, accepting, I presume, that even the best wizards cannot always control their emotions,' said Dumbledore calmly, as Fudge attempted to scrub the ink off his notes. (OotP, p.100)
That's probably the official line. In reality, at the time the Ministry believed that Harry was being targeted by Sirius Black, and went into a panic when Harry disappeared. Fudge is so relieved to find Harry at the Leaky Cauldron, that he doesn't press charges.
But more to the point, during Order of the Phoenix, Harry was being branded as a dangerous lunatic for contradicting the Ministry's line on Voldemort's return. When they had the chance to try to expel him permanently from Hogwarts and make him an outcast in the Wizarding World, they seized it. It was only because Dumbledore intervened and reminded them of the law that Harry's expulsion became a temporary suspension and his wand wasn't snapped immediately.
During Harry's trial, there is every indication that he was basically being railroaded. The time of the trial was abruptly moved forward three hours, presumably in the hopes that Harry would miss it and be tried in absentia. He is tried by the full Wizengamot, rather than the typical hearing with an official, and during the trial he is verbally abused and talked over.
Its strongly implied that the Minister of Magic Cornelius Fudge even changed the law specifically to convict Harry:
'Laws can be changed,' said Fudge savagely. 'Of course they can,' said Dumbledore, inclining his head. 'And you certainly seem to be making many changes, Cornelius. Why, in the few short weeks since I was asked to leave the Wizengamot, it has already become the practice to hold a full criminal trial to deal with a simple matter of underage magic!' (OotP, p.101)
tl;dr, the Ministry of Magic is corrupt. They liked Harry back when he blew up his aunt, but hated him when he fought the Dementors.
In Harry Potter and the Prisoner of Azkaban, Harry is in danger of being murdered, because they think that Sirius tries to kill him. Because of that, Fudge tries to protect him by making him live among other wizards. If he had banned him, Harry wouldn't be allowed to go to Diagon Alley.
In Harry Potter and the Order of the Phoenix, the suspected danger of Sirius is far less. And in the meanwhile, Harry fell in Fudge's grace because he said that Voldemort is back. Due to that Fudge would be in danger of losing his job.
So in PoA they tried to protect him, while in OotP they tried to distance themselves from him.
The whole Aunt Marge thing happened while the "serial killer" Sirius Black was on the loose. Fudge didn't have a reason to distrust him, so he didn't charge him for that.
However, during the patronus problem, Fudge, who is a complete coward and does not want to embrace the fact that Voldemort is back, seems to have taken a disliking to both Harry and Dumbledore. This shows that he is a biased judge who doesn't care about facts.
Hope this helped!