Isto é essencialmente o que eu tenho, um conjunto muito simples de três arquivos com o novo asp.net core 2.1 (na verdade, copiado e colado nos tutoriais):

public class Program
{
    public static void Main(string[] args)
    {
        CreateWebHostBuilder(args).Build().Run();
    }

    public static IWebHostBuilder CreateWebHostBuilder(string[] args) =>
        WebHost.CreateDefaultBuilder(args)
            .UseStartup<Startup>();
}

Então vai a inicialização mais simples

class Startup
{
    public Startup(IConfiguration configuration)
    {
        Configuration = configuration;
    }

    public IConfiguration Configuration { get; }

    public void ConfigureServices(IServiceCollection services)
    {
        services.AddMvc();
    }

    public void Configure(IApplicationBuilder app, IHostingEnvironment env)
    {
        app.UseMvc();
    }
}

E controlador de valores padrão

[Route("api/[controller]")]
[ApiController]
public class ValuesController : ControllerBase
{
    [HttpGet]
    public ActionResult<IEnumerable<string>> Get()
    {
        return new string[] { "value1", "value2" };,
    }
}

Não importa o que eu chamo, eu vejo no console o mesmo erro 404:

Application started. Press Ctrl+C to shut down.
info: Microsoft.AspNetCore.Hosting.Internal.WebHost[1]
      Request starting HTTP/1.1 GET http://localhost:5000/values
info: Microsoft.AspNetCore.Hosting.Internal.WebHost[2]
      Request finished in 105.0181ms 404
info: Microsoft.AspNetCore.Hosting.Internal.WebHost[1]
      Request starting HTTP/1.1 GET http://localhost:5000/api/values
info: Microsoft.AspNetCore.Hosting.Internal.WebHost[2]
      Request finished in 2.6016ms 404
etc

Eu tentei adicionar rota padrão tanto comapp.UseMvcWithDefaultRoute(); e especificando-o manualmente. Tentei remover os atributos da rota quando usei a rota padrão. Também tentei adicionarAddControllersAsServices(). Mas o resultado ainda é o mesmo - 404. Quando eu configuro o manipulador personalizado noapp.Run então funciona sem problemas.

csproj (substituí a dependência padrão do Microsoft.AspNetCore.All, mas o roteamento ainda não funciona)

<Project Sdk="Microsoft.NET.Sdk">

  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>netcoreapp2.1</TargetFramework>
  </PropertyGroup>

  <ItemGroup>
    <PackageReference Include="Microsoft.AspNetCore.App" Version="2.1.0" />
  </ItemGroup>

</Project>