Looks like one of core CiviCRM files (namely part of mySQL query at CRM/Contact/BAO/Query.php) has to be changed in order to achieve "Search results sort by Last Name". What would be the best (I mean, most proper) way in CiviCRM to do this?
The answer is already here. According to tiny mention at the bottom of http://wiki.civicrm.org/confluence/display/CRMDOC/Directories page, it is possible (and, more important, it works!) to copy modofyed core files to Custom PHP Path Directory (at civicrm/admin/setting/path?reset=1) , preserving original files/folders structure, so next time CiviCRM gets security updates, changes should be kept (unless original file / function major changes).