When you define a function `f`, you are (a) applying `Set` or `SetDelayed` to a pattern, (b) creating a rule, (c) associating the rule with a symbol (`f`), and (d) storing that in `DownValues` (usually).

    FullForm[Hold[f[x_] := x^2]]
    (* Hold[SetDelayed[f[Pattern[x, Blank[]]], Power[x, 2]]] *)

    f[x_] := x^2
    DownValues@f
    (* {HoldPattern[f[x_]] :> x^2} *)

###First question: is it true that "everything in Mathematica is ultimately stored as a rule?"

No: for example `2` is not a rule.  It's just 2.  So not everything is a rule, just functions.  Everything is an expression, ... some expressions (as a side-effect) create and store rules in DownValues.

###Second question: does Mathematica "gloss over" these rules by representing them as functions?
Yes and no.  They give you a glossy shortcut for input:

    f[x_] := x^2

instead of requiring you to write something like 

    AppendTo[Downvalues[f], f[x_] :> x^2]

There was one misunderstanding in your question; you asked about the output of

    FullForm[f[x]]

This is **not** showing you the definition of the function `f`.  It is showing you the result of applying `f` to `x`.  See the following:

    FullForm[f[2]]
    (* 4 *)

If you want to see the definition of `f` you should either use `Information` (which is glossy and not very useful) or `DownValues` which contains what you're after.

###Third question: does the by value/by reference question have any when you "pass" a value to a Mathematica function?
Work on the assumption that Mathematica is pretty smart "under the hood" about pass by value/ pass by reference.