I was wondering if there are any 4e adventures that are more like the Paizo APs. Does "War of the Burning Sky" fit this description? Are there other publishers out there, other than WotC, making high-quality adventures for 4e? If not, why not? It seems like a niche that perhaps someone could be successful in filling.
War of the Burning Sky is excellent. I switched from Scales of War after the heroic tier for exactly the same reasons you mentioned: lack of consistent plot, boring/non-existant NPCs, and lack of meaningful player options. I was tired of slogging through encounter after encounter.
War of the Burning Sky is the opposite. Great overarching and epic plot, lots of interesting NPCs, and real player choice. My group is just now finishing up the second adventure, which will bring them to level 7, and I'm very happy with it.
There are a few caveats: WotBS 4e is a conversion from the 3.5e version, and the early adventures reflect a lack of experience with 4e. The most notable problem is very uneven encounter design. New modules are still coming out and the latest ones look much better, but for the two adventures I've run, I've needed to tweak the encounters to make them work better. I've also cut out portions of each adventure, as they run a bit long in the heroic tier.
Bottom line: WotBS is excellent and I highly recommend it if you're willing to put in the work to make it shine.
Another option to consider is the Zeitgeist campaign saga that ENWorld is getting ready to put out. It's written for 4e by RangerWickett, the same person who did WotBS, so I have high hopes that it will have all the strengths of WotBS (interesting, complex) without the 4e design weaknesses. You can't run that one today, though.