Hacker News Reader

From memory, the Ubuntu Software Centre (under its former name) also pre-dated the App Store and variants.

Ubuntu Software Centre has been around since Oct 2009.

The former name was Gnome-App-Install, which has basically been around since Ubuntu started in 2004.