Custom Report By Relationship
This could be a place where it's just easier for the users to use an advanced search to bring up a list of households related to their own contact record. It's definitely possible that this puts too much onus on the user for your use-case, but it really only adds a couple of clicks over pulling up a report:

Advanced Search>Relationships tab
Relationship Type = your relationship from org to individual
Target Contact = the reps name

This would bring up the list of households the rep has a relationship for them. There are many ways to proceed in how they may 'tick off' these households for the year depending on the org process.

If that's too much for this set of users than your "p.s." is probably on the right track and writing a custom report is the way to go here. I would not create an entire extension for this.

If you're just adding results columns, it's usually pretty painless - the documentation is just kind of all over the place. The new .tpl file is a one-liner explained in Alastair's blog post. You can copy the base report (contact relationships in this case) .php file that is closest to what you want and then copy/paste the address block columns from a different report base that has them included.

I would like to add two resources to your links above that I found helpful to put it all together when learning custom report writing for myself:

https://artfulrobot.uk/civicrm-custom-birthdays-report

https://sf2012.civicrm.org/sites/default/files/slides/CiviCRM%20Reports-Customize%20and%20Extend.pdf