I'd like to record the interactions with different companies (e.g., the cable company) and document my interaction with them by recording the phone calls, uploading photos/pdfs of paperwork and set reminders... Is this functionality possible in Android, and if so, how would I accomplish it?
One way to do this would be with Evernote. You could organize it all sorts of different ways (eg. Organize companies by tag or by notebook... and a new note for each interaction...) and you can attach files (photos, pdf, voice memos...) to each note. As far as recording the actual calls, as Matthew Read suggested, take a look at this question.
If you are looking for a more integrated approach that works with the current call log and calendar you could consider an app like BizLog ($9). It doesn't do everything you want but it gets you very close. If this is more of why you are looking for I'd continue your search but use terms like CRM (contact relationship manager) and contact notes, contact log or contact management.