Não tem muito mistério. Sem conhecer os detalhes de como funciona a linguagem é só medindo e fazendo uma média pra ter uma base de qual é mais rápido.

Nos meus testes, com um milhão de registros, primeiro caso foi mais rápido (`Caso1()`), levando uma média de de 25ms a cada execução, o segundo (`Caso2()`) ficou com uma média de 40ms por execução.

Um detalhe importante é que você está fazendo bem errado no segundo caso, é melhor converter o retorno do `Where` para uma lista usando o método `.ToList()`, senão a comparação fica injusta porque vai ser necessário fazer dois _loops_ pela lista.

Usando `.ToList()` (`Caso3()`) cada execução levou uma média de 35ms.

O código que eu usei pra testar foi este:

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Diagnostics;
    
    public class Program 
    {
        static List<string> lista = new List<string>();
        public static void Main (string[] args)
        {
            PopularLista();
            
            Console.WriteLine(lista.Count);
            
            Caso1();
            Caso2();
            Caso3();
        }
        
        private static void Caso1()
        {
            var watch = Stopwatch.StartNew();
            
            var chaves = new List<string>();
            foreach(var item in lista)
            {
                if(!string.IsNullOrEmpty(item))
                {
                    chaves.Add(item);
                }
            }
            
            watch.Stop();
            var ms = watch.ElapsedMilliseconds;
            Console.WriteLine("Caso 1: " + ms + " ms");
        }
        
        private static void Caso2()
        {
            var watch = Stopwatch.StartNew();
            
            var chaves = new List<string>();
            var listaValida = lista.Where(x => !string.IsNullOrEmpty(x));
            foreach(var item in listaValida)
            {
                chaves.Add(item);
            }
            
            watch.Stop();
            var ms = watch.ElapsedMilliseconds;
            Console.WriteLine("Caso 2: " + ms + " ms");
        }
        
        private static void Caso3()
        {
            var watch = Stopwatch.StartNew();
            
            var listaValida = lista.Where(x => !string.IsNullOrEmpty(x)).ToList();   
            
            watch.Stop();
            var ms = watch.ElapsedMilliseconds;
            Console.WriteLine("Caso 2: " + ms + " ms");
        }
        
        private static void PopularLista()
        {
            for(int i = 0; i < 1000000; i++)
                lista.Add(i % 2 == 0 ? "Teste" : "");
        }
    }

[Você pode rodar os testes no repl.it.][1]


  [1]: https://repl.it/HI9r/1