With regards to Photoshop, I can see a plethora of things that can be improved upon. However, I have a much more difficult time conjuring up new features that would revolutionize digital editing where software tool sets are concerned. Quite simply, there are fewer workflow avenues to explore compared to a decade ago given the program's current state of maturity. Photoshop is the lord and master of the pixel and it is likely to remain so until whatever that can be regarded as current competition catches up in feature set.
In effect, this mirrors the Windows/Mac OS race in which Mac OS continues to make evolutionary strides, culminating in OSX, which eventually saw a momentary depletion from Apple's "bank of ideas". Subsequent versions of OSX became less appealing and even saw some periods of bloat. Fortunately, Apple was able to recognize the problem and focused their efforts on infrastructural improvements with Snow Leopard. Meanwhile, Windows, rather than innovating, simply borrowed feature after feature from Mac OS/OSX to eventually release what is considered to be the best version of Windows yet; completely inspired by Apple.
So, a sound strategy for competing with Adobe is rather than trying to outwit this Goliath with radical feature sets that only serve to break workflows, smaller companies should be copying the best of Photoshop's functionality and discarding the bloat while offering their package at a fraction of the cost.
Corel came very close to doing this with Photopaint (with version 4 even eclipsing Photoshop with superior handling of vectors) in the late 90s but faltered when the company elected to binge on an acquisition spree on everything from Raydream Studio 3D to Word Perfect.
Corel missed yet another golden opportunity when they picked up Metacreation's Painter. Had they combined traditional retouching tools and image editing utilities with the natural media features of Painter, Adobe would have had good reason to be concerned. Instead, Adobe finally wised up and quickly closed that gap upon the release of Photoshop 7 with the highly revamped brush engine (although Painter is still superior in this regard).
Currently, a vast majority of leading productivity software is published through American firms. Awash in a sea of conglomerates however, the United States is an incredibly difficult market to penetrate so I have doubts that a local countermeasure to Adobe will be found.
Instead, I would look to Europe and Asia which is experiencing a Renaissance of young software companies which are seemingly sprouting up en mass to challenge North American incumbents. Their work is most visible in the digital entertainment and film effects industry.
German based Maxon, the developers of Cinema4D, for an example, has just begun to make serious inroads in North America. Cinema4D is a revolutionary product that packages some of the best features found in XSI, Maya and 3DSMax into one easy cohesive workflow but without the legacy bloat currently plaguing the big three (starting to see a reoccurring theme here?). It also offers superior scene management and unmatched integration with Adobe After Effects. It still lags behind in terms of third party support but hopefully that will soon change.
As it stands, the biggest hurdle to overcome in terms of competing with Adobe is in an era where a single project often requires the use of several applications, almost everyone we know has the entire Adobe Creative Suite embedded in their workflow. As another poster already mentioned, why use Quark when Indesign is better integrated with Illustrator/Photoshop and is included with the CS bundle? Would you really want to do without the preservation of layer masks and styles that Photoshop offers when working with AE versus Paint Shop Pro? Would you risk losing valuable time by messing around with unamanged CYMK separations from another program?
Far from just the individual applications themselves, it is the entire Creative Suite taken as a whole, which will prove the most difficult aspect for opponents to crack.