Many transactions require no fee and are included in the next block, so paying a fee would almost certainly cause it to be included in the next block or two.

Are you sure it didn't make it into a block?  Check Block Explorer:
 - http://www.blockexplorer.com

If the transaction is still queued up for inclusion, it will likely appear here:
 - http://bitcoincharts.com/bitcoin/

Just to make sure that you are describing the problem correctly, understand this:

- http://en.bitcoin.it/wiki/Confirmation

So there is no amount of fee that will cause at transaction to "confirm" any earlier than 6 blocks.  

What I thought you were describing is that the transaction did not even get included into a block right away.  That can happen unless a fee is paid.  Before a transaction is included in a block, it likely will appear here:
  - http://www.bitcoincharts.com/bitcoin

The reason there's no "price versus time" chart is because, for the most part, all transactions get into the next block or two regardless of the fee paid.  If no fee was paid and the transaction is a low priority transaction, then it could end up queued.  There already is a solution for that though -- next time make sure to pay the minimum transaction fee when sending payment and the problem is solved.  Keeping your Bitcoin client current may be useful so that if a fee is necessary, the client will make an accurate fee suggestion.
  - http://en.bitcoin.it/wiki/Vocabulary  (see "priority").

At some point, when transaction fees become more important to miners, the transaction fee could affect how soon a miner includes the transaction.  At the present and near-term future (next years or so maybe?), it isn't an issue, as far as I'm aware.   [related: http://forum.bitcoin.org/index.php?topic=14571.msg196574#msg196574 ]