You want to insulate first, otherwise anything else you do is just going to be pushing heat through your exterior walls. You should be able to get spray in insulation in those walls without needing to full tear down the drywall. Typically you’ll get a 1-2” hole on the top and bottom of each stud bay for foam to be sprayed in, then you patch that. It can be pricy up front but should pay off super quick if you have none right now (I’m still getting over 3,000 kWh… that just seems like an insane amount of electricity to use).
A mini split likely won’t help, you’ll just lose the cooling without insulation the same as without the mini split. You may want to look into balancing your ducting once you get the house insulated if you still have rooms that are too hot or cold. The bricks should help to stabilize temps and reduce swings over time but the effect is likely small and should be able to be ignored once you insulate.