I like using http://www.generateit.net/mod-rewrite/ . Pretty easy to figure out how it's done when you used that tool 2 or 3 times.
You can define which parameters take which "spot"
so to get your:
domain.com/?page=login
domain.com/?page=user&uid=2
to:
domain.com/login/
domain.com/user/2
You can use:
RewriteEngine On
RewriteRule ^([^/]*)/([^/]*)$ /?page=$1&uid=$2 [L]
Your "page" problem looks a bit more difficult.
You would have to add rewrite rules for each "page" or file I guess.
At least I don't know how to do that.
If it's a folder you could solve that by giving the folder its own .htaccess
Edit:
RewriteEngine On
RewriteRule ^Page/([^/]*)/([^/]*)/([^/]*)\.html$ /Page.php?a=$1&b=$2&c=$3 [L]
Might work. I added Page/
under prefix
in the generator