Applying functions to leaves of nested list structure, when these leaves are more complex expression trees

ReplaceAll with replacement rule {x_, y : Except[___List]} :> h[x]:

{{a, b}, {c, d}, {{d, e}, {f, g}}} /. {x_, y : Except[___List]} :> h[x]

{h[a], h[c], {h[d], h[f]}}

{{u[a], u[b]}, {u[v[c]], d}, {{d, e}, {f, g}}} /. {x_, y : Except[___List]} :> h[x]

{h[u[a]], h[u[v[c]]], {h[d], h[f]}}

You can use Replace with a level of All:

Replace[
    {{a,b},{c,d},{{d,e},{f,g}}},
    {x:Except[_h],y:Except[_h]} :> h[x],
    All
]

{h[a], h[c], {h[d], h[f]}}

Using Replace with a level of All does a depth first (bottom up) replacement. Using ReplaceAll instead uses a top down replacement:

ReplaceAll[
    {{a,b},{c,d},{{d,e},{f,g}}},
    {x:Except[_h],y:Except[_h]} :> h[x]
]

{h[a], h[c], h[{d, e}]}

You can use the Listable attribute. Give the attribute to h or a wrapper-function as below:

Module[{hh},
 SetAttributes[hh, Listable];
 hh[x__] := h[x];
 hh@{{u[a], u[b]}, {u[v[c]], d}, {{d, e}, {f, g}}}
 ]
(*  {{h[u[a]], h[u[b]]}, {h[u[v[c]]], h[d]}, {{h[d], h[e]}, {h[f], h[g]}}}  *)

Also:

Function[, h[##], Listable]@{{u[a], u[b]}, {u[v[c]], d}, {{d, e}, {f, g}}}