App Store was obvious as Linux user. In Windows and Symbian users has to search for installer. Out of commercial looks like Valve was first. I've never seen Windows Marketplace. Nokia took so long to make obvious thing - you have to review and sign application by Nokia (Symbian 9.1, 2005 [0]), but host by yourself.

Valve Steam - announced on March 22, 2002, released for beta testing the same day. [1]

Windows Marketplace - announced on July 12, 2004, launched on October 12, 2004 [2].

Nokia Ovi - announced on 29 August 2007, public beta on 28 August 2008 [3].

iPhone App Store - opened on July 10, 2008 [4].

[0] https://en.wikipedia.org/wiki/Symbian

[1] https://en.wikipedia.org/wiki/Steam_(service)

[2] https://en.wikipedia.org/wiki/Windows_Marketplace

[3] https://en.wikipedia.org/wiki/Ovi_(Nokia)

[4] https://en.wikipedia.org/wiki/App_Store_(iOS)