What are the pros and cons of each? Does it make any sense supporting both? Which is easier for users/to implement?
It depends on your target audience - there's no right answer. Especially if you are trying to use your website as a business, you need to focus on your audience. Ease of implementation should be a secondary concern, especially since both Facebook Connect and OpenID have been implemented by a number of sites, you should be able to easily get tutorials.
It sounds to me like you don't want to manage your own users and registration, which is getting easier with more companies supporting things like Facebook Connect, OpenID, and other shared login.
But in order to determine which one you use depends on your target audience. Stack Overflow went with OpenID and it worked out for them because the audience was of a technical nature. Most people either had an OpenID, were somewhat familiar with OpenID, or were comfortable enough reading about it, understanding what it did, and signing up for another service. Now that services like Google are supporting OpenID, it's becoming much more widespread.
On the other hand, if your target audience falls into Facebook's typical audience (I'm not sure what the demographics of Facebook are, exactly - I'm sure you can find that information out, or at least get estimates that are reasonably accurate), you might want to support that instead of OpenID.
If you have sufficient time and resources, though, there's no reason not to support multiple authentication standards. But if you had to pick one, go with the one your target audience uses.
I think a concern should be not the implementation of these services, but how you display them to your user so that they understand that they can log in to your site using another service. This will depend a lot on your target audience. Your log in page(s) should be explicitly clear in language that the user is familiar with as to what they are doing, especially if the target audience is non-technical.
I think OpenID and Facebook log in integration are about equal in their complexity for the site user. Either can be useful, what really matters is what is your target audience.
If your goal is to do something that works well with Facebook and is for the general masses then Facebook integration is the way to go. Also, will the people using the site possibly be friends on Facebook?
If your goal is to reach a somewhat technically savvy user base that won't be driven to your site mainly from Facebook then there is more value in OpenID
Finally, if your site is for the general public including people who are not internet savvy then there is little value in OpenID because many people don't know what it is and won't use it. Facebook log in integration has some value because most of the US population knows what it is and has an account in this case.