How should I generate a report (or view) showing contacts and people they have relationships to?
I will add this as an answer so i can add the screenshot. You 'should' be able to filter by Groups in a civicrm contact based View. In the screenshot you will see i have both Group Name and Group ID set as fields, and have Group ID set as an Exposed Filter. Hope that helps if only to confirm that something is amiss in the world of Views for you. 

(Note: on the first site i went to do this on I also did not have them available, but that is a Pantheon based site where things keep changing on me, on the second which is a standard-hosted site it all worked as expected. So you may not be alone with the Group fields being unavailable)