Textlabel getting moved each time a new one spawns?

Well, I see no attempt of you trying to push its position down. What you need to do is set a variable, that would contain the last TextLabel, or its position. So:

LastLabel = nil

game.Players.PlayerAdded:connect(function(player)
    local label = Instance.new("TextLabel",script.Parent.SurfaceGui.Frame)
    label.BorderSizePixel = 0
    label.BackgroundTransparency = 1
    label.Size = UDim2.new(1, 0, .05, 0)
    label.Font = "ArialBold"
    label.FontSize = "Size36"
    label.TextColor3 = BrickColor.White().Color
    label.TextStrokeTransparency = 0.5
    label.Text = player.Name.." - "..player.userId
    if LastLabel ~= nil then
        label.Position = LastLabel.Position + UDim2.new(0, 0, .05, 0)
    end
    LastLabel = label
end)

game.Players.PlayerRemoving:connect(function(player)
    if script.Parent.SurfaceGui.Frame:findFirstChild(player.Name.." - "..player.userId) then
        script.Parent.SurfaceGui.Frame['player.Name.." - "..player.userId']:Destroy()
    end
end)