This is not so much a function of ! as a function of what is or is not true in javascript.  If you are familiar with casting, the coercing of a variable to a specific type, then the following should be reasonably clear to you.
! only operates on booleans.  Therefore, any variable you apply it to that is not boolean is first coerced to be a boolean before applying !.  To relate this to your examples:
Boolean(undefined) == false 
undefined is sort of like null in javascript (there are some differences but that's a different topic).  It should make sense that the Boolean equivalent is false. undefined goes beyond just absence of value, it declares the variable you are trying to use doesn't even exist.
Boolean(function(){}) == true
Functions are objects in javascript. Even if it's empty, it still has some basic properties common to function objects and therefore its Boolean equivalent is true.  It's not nothing so it's something.
Boolean({}) == true
Like an empty function, {} defines an empty object. However, it still has some properties common to objects in javascript. It simply has no custom properties.
Boolean(null) == false
As I mentioned for undefined, null is similar but not quite the same. It indicates the absence of value.
Boolean(()) // error
() on their own don't really mean anything.  You need something between them to make the syntax correct so this has no bearing on your false/true question. () alone is simply a syntax error.
Boolean("false") == true
"false" is a string.  Just because it contains the letters f,a,l,s,e does not make it the same as the Boolean value false.  A non-empty string is something and therefore coerces to the Boolean true.  Note strings are kind of special objects in that an empty string "" coerces to false but an empty object, {}, as mentioned, coerces to true.
Boolean(false) == false
This one should be clear.  false is already a Boolean so casting it doesn't change its value. It's still false.
From that, you can see how applying ! to each case would give you the results you have seen.
For further reading, here's a pretty good article on type coercion in javascript
UPDATE:
In regards to your String questions. There is a different between a String object and a string literal (something surrounded by quotes).  You can create a String object from a string literal but a literal is not automatically an object.  The same is true of numbers in javascript. JS has a Number object but you will often define numeric literals.  The behaviour of Number is consistent with what you've seen with String:
alert( new Number() == 0); //true
alert(!0); //true
alert(! new Number()); //false
However, as you astutely mentioned in your comment:
alert( new String() === ""); //false
As the types are not the same; object vs. literal.
In general, Boolean(some_object) will always evaluate to true but depending on the exact value, Boolean(some_literal) may evaluate to false.
ADDENDUM
Just because I shot myself in the foot earlier this week I thought this would be a useful piece of information to add.  In most languages an empty array, [], will be coerced to false. However, in Javascript, arrays are objects so even the empty array coerces to true.  One to watch out for.  When switching between js and the various server side languages it's easy to make a slip up along the lines of if(!maybe_empty_array){...} which will never pass because maybe_empty_array will always coerce to true. Instead you should do if(maybe_empty_array.length){...}.  If the array is empty its length is 0 which safely coerces to false.