Is there a way automatically get sort name and greetings to be correct for households?
Have you tried changing the sort name so the results show up in alphabetical order? (Administer/Customize Data and Screens/Display Preferences). I set it like this:

{contact.last_name}{, }{contact.first_name}{ }{contact.middle_name}


In that way my contacts are sorted on the last name and I also include the middle_name (which means something in Dutch so it becomes 'Boer, Jan de').

But perhaps you tried that and your problem is somewhere else?