That would depend on their skill, IMO, but I think you've identified the best books already.
'Testing Computer Software' is, IMO, best for total novices, though I feel it's getting older and have been looking for something more up-to-date to recommend. 'Testing' is too strongly tied to slower software development life-cycle models like waterfall in the later sections on documentation, and makes references to paper bug reports and other arcane and ancient processes. However, it's still the best book I've seen for the basics like boundary testing, equivalence classes, white box / black box, areas of testing, and so forth.
I tend to recommend 'How We Test Software at Microsoft' for testers with some experience already, because I think the challenge for skilled junior testers and mid-level testers is to get themselves thinking about the different ways they can approach a problem, and I think "How We Test" gives enough of a variety of techniques to help get people's minds churning. Applying new techniques is a great first step towards thinking critically about the best way to test, like senior testers need to be able to do. This might pair well with 'Agile Testing', which fills a similar niche - or even be replaced by it, depending on your company's development style. I like the combination of the two; they show very clearly how testing approaches can be very different and still get the job done well. Both are geared towards testers who use some level of automation in their testing; I think there are some good books on exploratory testing that could be useful for manual testers at this stage of their career, but I don't know what they are.
'Lessons Learned in Software Testing' is my top pick for upper-mid-level to senior testers, closely followed by 'Beautiful Testing'. 'Lessons' is great for moving people from testing as their boss directs to thinking themselves about what the best way to test is, and why. 'Beautiful Testing' is great for going more in-depth into a variety of experienced testers viewpoints on specific topics, which gives a good feeling for the variety of skills that make up a truly great tester - from techniques to communication. 'Lessons' wins for me mainly because it covers more ground and offers more pieces of wisdom, although with less depth.