What's the cleanest functional-programming style way to perform this list operation?

Is this what you want?

Min /@ Tuples[Range[1, 4], {2}] // Mean
15/8

Pinguin Dirk forced me to post this:

f[n_, k_] := Range[n, k].Reverse@Range[1, 2 (k - n + 1), 2]/(k - n + 1)^2

it appears to be 10 times faster than:

Plus @@ Times @@@ Transpose@{##, Range[2 Length[#] - 1, 1, -2]
                            }/Length[#]^2 &@Range[50, 10000] // AbsoluteTiming
{0.010001, 100500125/29853}
f[50, 10000] // AbsoluteTiming
{0.001000, 100500125/29853}

If it should be functional programming style, try this:

Plus @@ (Min @ #1  #2& @@@ {
  {{1, 1}, 7}, {{2, 2}, 5}, {{3, 3}, 3}, {{4, 4}, 1}})/Length[rolls]
15/8

rolls = Tuples[Range[1, 4], {2}];
tally = Tally[rolls, Min[#1] == Min[#2] &];
lis = {{{1, 1}, 7}, {{2, 2}, 5}, {{3, 3}, 3}, {{4, 4}, 1}}
Total[Min@#[[1]]*#[[2]] & /@ lis]/Length[rolls]

Which gives:

15/8