OMG, the holy grail. I hear you.
I admit I am in awe of your ability to keep mules on the foot! I once had a pair of mule/slides that stayed on (more or less) but every other pair came off.
So, if Madewell has a cute version as Lisa says, definitely try!
When I lived in Ontario I was like you -- it was boots or booties or sandals all the time. I had about one transitional shoe/ sneaker per year. And really not much need for any more, although there would be about 3 weeks per year when I would feel a bit helpless in the shoe department.
Now my life is even more casual than yours, I suspect -- no need to go to an office, so I've been wearing nothing but fashion sneakers for weeks.
Considering: knit flats (would they hold up in rain?), simple loafers like the Emmelines, slingbacks, shoes with elastic backs. I had some Trotters pumps that worked somewhat better than most a few years ago.
Knit flats wouldn't hold up well in rain. I don't think. But they might be comfy. I love loafers but have never yet had a pair that stayed on my foot. I think it's partly that they are flat -- not enough of my foot contacts the shoe to hold it on (due to my arch, which, weirdly isn't especially high, but is obviously higher than average). Ditto slingbacks -- impossible for me. I adore them and every 6 years or so I make the mistake of buying a pair. I have not tried elastic backs but think they might be promising, if the elastic didn't dig in too much.
I also wear prophylactic bandages for blisters with new footwear (or even footwear I have not worn for a while). And once I'm done with bandages, I use body glide on the heels. I hear you about inserts not working well. The little heel thingies never work for me. I sometimes (rarely) have some success with a Superfeet or a heel cup (for plantar fasciitis) but this depends on whether the style will accommodate it.
Brands that might work: Stuart Weitzmann (pricey, but maybe at the Rack?) Munro, maybe Ecco (the heels are a bit narrower but fronts might be too wide for you without inserts). I'm not a whole lot of help here!
The transitional "shoe" that I found pretty useful for a few. years was one of those sandal booties. Maybe not the height of fashion at the moment but not "out of style" and it worked well for me for a wide variety of situations.
I'm also wondering about a fairly covered espadrille -- could do the job? Maybe one without a peep toe but with a solid toe.