The idea of applications on the phone was something blindingly obvious to me ever since my first Nokia 3410 I had as a kid. The phone had a bunch of distinct functionalities other than making calls, which you could invoke through a menu. Why shouldn't I be able to add new ones? Write new ones myself?
Installing custom software was later normalized when phones gained ability to run J2ME applets. By the time iPhone was conceived, it was an expected feature.