Columns available for sorting in CiviReport seem arbitrary/random
Well, I started to give an answer, then started digging, and eventually found a bug that affects this particular situation.  I've reported it as reporting#6 and submitted a fix.

It turns out that address_name is defined twice, accidentally.  The first time it's correct; the second time is incorrect, and prevents the address name from being sortable.

I've submitted a fix, which should be in the 11/7/2018 release (CiviCRM 5.7) - but for now, open CRM/Report/Form.php in your CiviCRM root and delete lines 5517-5522.  Note how street_name is also defined earlier, with is_order_bys set to TRUE, which makes it available for sorting.

To answer your other questions:


Custom fields will be available for sorting (and in reports generally) if the "Searchable" option is selected for the field.
There's no shame in connecting a third-party MySQL reporting tool to CiviCRM!  If you use Drupal, you already have a great one in Views; other folks like Tableau and Pentaho BI.  A dedicated reporting tool will always be a great choice.


Some additional thoughts:


Not every report uses this function to determine the fields to include!  In olden days, each report defined its own address fields; now the best practice is to use this function.  This fixes a bunch of reports, but not 100% of them.  Notably, it fixes "Constituent Sumamry" and "Walk List".
Check out the Walk List report, aka "Survey Report (Detail)", since I suspect you're doing a walk list.
If you ARE doing a walklist, upgrade to CiviCRM 5.5+, because there's a bug fix that lets you sort by odd/even street numbers.