https://en.m.wikipedia.org/wiki/Category:1995_software
What software specifically do you recall being "an order of magnitude more complex" than today's popular web apps?
I do remember using Maya on Irix in '97 or so and it was already pretty amazing. It was built off earlier applications like power animimator, which was started in '88:
https://en.wikipedia.org/wiki/PowerAnimator
Maya had a customizable interface, and neat things like pie-menus, although not invented there.
One major difference in 1995 applications is that almost none of them were collaborative or synced with a remote server. They were all isolated applications that worked entirely in a local context. They could be programmed to a single target platform on perhaps one to three screen resolutions (640x480, 800x600 and 1024x768). They could all work under the assumption that one style of input was being used (mouse and/or keyboard). They all could use simple built-in dropdown context menus. They could all render to a canvas context graphics with much of the heavy lifting assumed by the operating system itself.
Advanced collaboration still in the future, this era was more like chat and file transfer. I think you could mark up Word docs from a network drive at some point.