Introduction to Programming with Pseudocode
This is exactly the approach taken by the Introduction to Algorithms course at MIT—or at least it was the case back in the early 2000's. The book by Cormen et al. takes a decidedly agnostic approach to programming, and presents everything in terms of pseudocode, rather than adopting any particular programming language.