Okay, I gave it a shot:

sub f {
# 38 characters
# ($a,$b)=@_;$a=~s/_/./g;grep{/^$a$/}@$b

# UPDATE: After seeing everyone use y///, I decided to join in:
# 37 characters
($a,$b)=@_;$a=~y/_/./;grep{/^$a$/}@$b
}

sub g {
# 186 characters
# my($c,$d,@e)=@_;my$g='[^'.(join'',@e).']';$c=~s/_/$g/ge;my(%f,$j,@i)
+;for$j(grep{/$c/}@$d){map{$f{$_}+=($j=~s/$_/$_/g)}(grep{/$g/}('a'..'z
+'))}@i=(sort{$f{$a}<=>$f{$b}}keys%f);return pop@i

# UPDATE: I forgot that you didn't have to join the list...
# 166 characters
my($c,$d,@e)=@_;$c=~s/_/[^@e]/ge;my(%f,$j,@i);for$j(grep{/$c/}@$d){map
+{$f{$_}+=($j=~s/$_/$_/g)}(grep{/[^@e]/}('a'..'z'))}@i=(sort{$f{$a}<=>
+$f{$b}}keys%f);return pop@i
}
[download]

These seem to work with my test cases, but I'm sure someone can break them... This was a fun one, thanks Masem.

Update: There weren't any answers when I started, and I noticed after I finished posting that my solution to Part 1 is almost the same to japhy's. Before anyone leaves a note, I didn't rip him off... Actually, I'm pretty pleased with myself that I had the same idea as the Lord of all Regexes himself.

"We're experiencing some Godzilla-related turbulence..."