According to the blog post about this (before the update was released) the higher importance contacts would have their "best" missions limited by your personal relation with them, honestly I've also yet to find a noticeable difference.
Supposedly higher importance trade contacts get you more valuable commodities in larger quantities, military contacts get you stronger bounties, that sort of thing. Why do you get a contact of one tier or another I've never seen explained though.
I think contact importance would be better tied to getting special privileges within the faction they belong to. Cheaper weapons and hulls, easier smuggling (patrols might look the other way or reduced suspicion), better commodity prices on the planet they contact is based, locking the ability to avoid AI inspections behind the contact system could be interesting, and finally and most important of all, getting all the discount lobster you could ever want OH LUDD YESS DADDY ANDRADA! Ehm ehm...anyways, missions are nice but giving you the feel of getting "pull" through them would make them amazing. Also having them depend on your faction reputation as you said could be interesting, indirectly or directly making developing one contact let you access higher tier contacts. Somewhat grindy but could be fun i guess. If not then, tell us how to reliably get those "very important" shinies so we don't bother with the unimportant peasantry.
