Alright, I've been making progress.
One thing I've noticed, though: If you want to edit a page, it forms a different kind of link:
http://foo.com/mediawiki/index.php?title=Main_Page&action=edit
So instead of the index.php/Main_Page format, I have to deal with ?title=*&action=*
I tried to make another .htaccess rule, but it doesn't work :[
I've tried these:
RewriteRule ^mediawiki/index.php(.+)$ index.php?wiki=$1 [R=301]
RewriteRule ^mediawiki/index.php?title=(.+)$ index.php?wiki=$1 [R=301]
I even tried just taking ANY /mediawiki address and rewriting it... would this be the best option?
RewriteRule ^mediawiki/(.+)$ index.php?wiki=$1 [R=301]