Calculating the connectance of a matrix iteratively
Without installing bipartite and getting into the exact details of what the actual calculations are looking to do, there are a few things that jump out at me that might help you.

Growing the Object (connectMatrix)

It looks like you're in Circle 2 - Growing Objects of the R Inferno.
Specifically, the line where you've got:

#Stitch matrix together  
connectMatrix[k,] &lt;- c(site, method, subSize, con)


In that scenario, every time you add another row to the connectMatrix, you're expanding and fragmenting the memory you're using, which as you've observed starts out okay but then starts to really drag. Here's another resource on that same issue, and a much less intricate Stack Overflow question.

nested for loops

You've got three layers of nested for loops

for(i in 1:length(unique(df$SiteMethod))){

    #subsetting dataset
    ...
    ...
    ...


    for(l in 1:numRep){
        #Beginning calculation loop
        for(j in 1:length(size)){

        ...
        ...

        }
    }


The outside for loop jumps out at me as something the plyr package might be good for -- essentially it looks like you're splitting the main dataframe into subsets, then doing things to it (the meat of your second and third for loops). Basically, plyr was designed for splitting-applying-and combining, and there's a really great paper on how to implement it.

You may be able to do two (or maybe even three) layers of splitting-applying-combining.

If the data lend themselves to grouping operations, those tend to help, too, but it doesn't seem like it based on the comments in the code.

Parallel processing

If, after you've optimized for not growing the object and chunked the code for splitting/combining (or another method of getting to the same outcome), you're still not at the level of performance you're looking for, you can journey into parallel application.

Basically, parallel application works well when you're using apply or plyr approaches and you can convert over to mcmapply or one of the other parallel approaches. 

For example, we use mcmapply in production at work to take a 30 minute process and trim it down to about 6 minutes. Parallel processing tends to be worth it (in my personal experience) only once you've done everything else you can to get to the best speed you can without parallelizing - it tends to be more work to get it right, and, as a bonus, once you've done the other things it tends to make it easier to convert the process to run on multiple cores.

Finally, Efficient R is a good general resource on optimizing R processes.