Start your searches for partner flights by using their websites. That will work pretty well for Delta and NW/KLM. The NW/KLM site will also show some of the AF flights.
If you can make it to Europe you should be able to pick up the intra-Europe flights using the partners rather than having to buy a different ticket to make it work. Also consider trying for Air Europa for the intra-Europe connections as necessary.
You will definitely have to call to book and you might have to call to check availability for some of the carriers (like Air Europa).