When you say software, I'm not sure if you mean software as in Firmware ( the OS ) or software as in software applications:
There are other phones around who's firmware can be updated easily.. for example, SonyEricsson and Nokia smartphones: Plug in your phone , load the Software Updater, the firmware is downloaded, and your phone firmware ( software ) is updated. Simple. Microsoft smartphone etc can also up date their firmware too.
OTA ( Over The Air ) firmware updates are now ( or very soon ) possible, using the phone 3G / WIFI ability to download the firmware straight on to the phone itself. Exactly how the PSP does it, for example.
So, no, the iPhone isn't the first.
When it comes to updating the software on the phone ( i.e., applications), thats nothing new. Most smartphones can download an app from internet directly on the phone and install without touching a computer.
On another note, can the iPhone's memory be backed up, so if something does go wrong, all your preferences etc can be restored?