Surface touching something?

Move it

This assumes that your part isn't actually intersecting with another part, and that you don't need the part which it's touching.

local function IsTouchingForward(p, closeness)
  local closeness = closeness or 0.1;
  local tmp = p.CFrame;
  local tmpp = (tmp*Vector3.new(0,0,-closeness);
  p.Position = tmpp;
  local r = p.Position ~= tmpp;
  p.CFrame = tmp;
  return r;
end;

This checks if there's something which it can collide with 0.1 studs infront of it. You can change the vector and closeness to tune it to suit.

This is a fun question!

Another possibility is to do some plane intersections along with culling. The calculation is way more intense, but the answer is more accurate and allows you to test specific parts. I'd still rcmd using eLunate's tho if it doesn't matter.

function planeIntersect(point, vector, origin, normal)
    -- see this blog post: https://scriptinghelpers.org/blog/silhouettes-and-shadows
    local rpoint = point - origin;
    local t = -rpoint:Dot(normal) / vector:Dot(normal);
    return point + t * vector, t;
end;

function surfaceCollision(part, normalid, otherpart)
    local planes, corners = {}, {};
    -- get the planes that make up the surfaces
    for _, enum in next, Enum.NormalId:GetEnumItems() do
        local lnormal = Vector3.FromNormalId(enum);
        local wnormal = part.CFrame:vectorToWorldSpace(lnormal);
        local distance = (lnormal * part.Size/2).magnitude;
        local point = part.CFrame.p + wnormal * distance;
        planes[enum] = {
            normal = wnormal;
            point = point;
        };
    end;
    -- get corners of thing you're checking
    for x = -1, 1, 2 do
        for y = -1, 1, 2 do
            for z = -1, 1, 2 do
                table.insert(corners, (otherpart.CFrame * CFrame.new(otherpart.Size/2 * Vector3.new(x, y, z))).p);
            end;
        end;
    end;
    -- collision lines
    local attach = {
        [corners[1]] = {corners[3], corners[2], corners[5]};
        [corners[4]] = {corners[3], corners[2], corners[8]};
        [corners[6]] = {corners[5], corners[2], corners[8]};
        [corners[7]] = {corners[3], corners[8], corners[5]};
    };
    -- check each line against the surface plane chosen
    for point, set in next, attach do
        for _, corner in next, set do
            local v = corner - point;
            local p, t = planeIntersect(point, v, planes[normalid].point, planes[normalid].normal);
            if t <= 1.001 and t  >= 0 then -- minor margin of error to account for float math error
                local pass = true;
                for key, plane in next, planes do
                    if key ~= normalid then
                        local r = point - plane.point;
                        if r:Dot(plane.normal) >= 0 then
                            pass = false;
                        end;
                    end;
                end;
                if pass then return true; end;
            end;
        end;
    end;
    return false;
end;

Example in action: http://i.imgur.com/6aeVvMe.gif