To sort by locality with the order_by shortcode option you need to use the
city option, like so:
[connections str_work_phone="Office Phone" str_work_addr="Street Address" str_other_addr="Mailing Address" category=3 order_by="city|ASC"]
In older code I used city instead* of locality and the sort option is pretty old. In many places in the old code I have aliased city and locality so they can be used interchangeably but this was never done for the sorting.
Hope this helps!