Add my own custom fields for profile types

We're going to have profile types of users and companies. How easy would it be for me to write a plugin or some kind of custom field for profile types where it basically is something like:

"Associate with users" <--and configure it to be of a specific profile type (in this case, company type)

And a popup would show of all users to associate with, so users of regular profiles can associate with users of company profile type. So like John can associate with Burger King for example.

Or is this not possible at all because it's core code and would require customization?

Thanks. And if it is possible, do you guys do development services and could I pay to have it done?