There are actually very good reasons to use the partition function over the minimum free energy, at least for strands of length N > 100. If you look at the Boltzmann distribution P(s) = e^{-E(s)}/Z, the probability of being in any given state goes like 1.1*10^{-N/59} (see attached pMFE2.pdf). For many of these strands, there exist multiple stable macrostates, the most stable of which may not contain the MFE state because they get their entropic weight from multiplicity of states near them, rather than having the lowest energies (see attached ensemble-centroid.jpg). Predicting structure by sampling from the boltzmann distribution and clustering structures has been shown to be more accurate than just the MFE calculation. Check out Ding and Lawrence (2005)
http://www.ncbi.nlm.nih.gov/pubmed/16043502. There are also many other reasons not to trust MFE computations, mostly because the energy model of RNA has tons of error and uncertainty which the MFE is *really* sensitive to, while partition function probabilities are a little more robust. I wrote about this extensively in my thesis. You are correct though, it is a difficult computation because there are many states, specifically O(1.8^n), but there exist dynamic programming algorithms that compute it in O(N^3).
I was thinking more of basic DIY projects that I could do and maybe extend with RNA structure prediction, or other molecular dynamics tools. I recently read about BioBricks, thought I might be able to help design some standardized parts, but I would have a hard time extending something I haven't touched yet. I want to get my hands dirty, and through that figure out something I could use my computational knowledge for. I am just completely in the dark with how to get started experimentally.
Mike