NOTE: I know you may not be able to divulge what your package does, which increases the answers usefulness generally, but also abstracted from your intended goal. It also significant increased the length of the answer for the sake of clarity. Feel free to comment at me or we can have a chat sometime if you'd like more details specific to your use case.
Part I
Two or Three Custom Objects?
Are the clients allowed to "monkey" with the objects? If you create the objects by Apex Code, they will be unmanaged, meaning the users could just delete the object or make a breaking change to the object, causing your code to fail. Instead, consider including all three objects in the package (the administrator could just turn off C if they don't need it), or you can create two to five (or more?) managed packages.
Here's how you might lay out multiple packages to work together.
Two Packages
Package 1 contains A and B, and all the relevant code to make A and B work. Package 2 contains C, and all the relevant code to make C work. Package 1 may need to detect if Package 2 is also present, in which case it can use Dynamic Apex Code to call the hooks in Package 2 appropriately; if it is strictly trigger based, this may be unnecessary, since Package 2 could contain a trigger that executes on A or B.
Three Packages
Package 1 contains the objects A and B, and any triggers for A and B that C does not need. Package 2 contains C, and any triggers specific to additional functionality of C. Package 3 contains all of the code common to A, B, and C, and uses dynamic Apex Code to avoid a hard-link to C, which would make Package 2 required.
Four Packages
Package 1 contains the objects A and B, and no code. Package 2 contains the object C, and no code. Package 3 contains all the code that leverages only A and B. Package 4 contains all the code that leverages A, B, and C (basically, the code from Package 3 with modifications to support C).
Five Packages
Package 1 contains the objects A and B, and no code. Package 2 contains the object C, and no code. Package 3 contains A and B specific code. Package 4 contains C specific code. Package 5 installs last and essentially links package 3 and 4 together dynamically.
Benefits
Each design has some benefits and drawbacks. More packages means that more initial setup work must be done, but eases the burden of keeping things in line. If you have the time, I would personally recommend the three or five package approach; the former offers flexibility at the small expense of time, and the latter offers deeper separation of the packages, but is most likely overkill in all but the largest projects.
Drawbacks
Multiple packages means more work keeping them all aligned, and version alignment would be a nightmare. The five package version suffers from this the most, while the two package version would be easier to maintain. This "version problem" is especially true for the five package version, because, unless they were upgraded in order and consistently, it would be hard without a spreadsheet to keep track of which versions are compatible with each other, since salesforce.com requires that the minimum version be the minimum version of the source organization at the time of the upload.
Part 2
Custom Lookups
You could create a bunch of code for this, but it is probably unnecessary (and I have yet to see a single product that does this!). Normally, creating the fields are done post-installation anyways, and is usually included in the "installation guide" for the app. Administrators expect to have to visit setup and spend a few minutes creating fields, adjusting layouts, etc, so it would probably not be worth the man hours to automate this when it would take just a few minutes of each administrator's time to do it manually.
That said, if you do want to implement this, keep in mind that those fields will be editable by any administrator and could break at any time if an administrator makes a mistake. Your code must be prepared for the possibility that this may happen. Also, you won't be able to package any reports for A, B, or C, because they will automatically break when the sharing model changes from "master" mode to "detail" mode (because master-detail fields alter the object's underlying properties, and so salesforce.com will deem those reports "obsolete").
Your Visualforce page would use Metadata Apex Code (see other answers on this forum for ideas on accessing the metadata API through Visualforce) if you decided to create the page. It is not difficult, precisely, but you will find that a proper implementation will probably be relatively time consuming as opposed to simply giving the administrator the responsibility of creating the fields.
Best Answer
It would be really weird to have lookups silently count as ext. id fields...
Try performing describe calls on all objects in your package that you suspect to clash? I have a custom field marked as "External Id", "Unique Case Insensitive" and I get this:
EDIT: There are 3 unique / ext. id fields per object. Ask support for increase.
BUT
How many formulas do you have on the objects that can be "common" with the other package. And do these formulas utilize in total 10 lookups to different places? (scroll to "Formulas: Number of Unique Relationships Per Object" text)?
I can imagine this being different kind of limit (put in place because too many lookups / formulas make joins in the underlying database extra painful to retrieve data). In that case you might have to consider rewriting some of your lookups into fields updated with triggers (always pain in managed package as I understand).