Which version of X introduced feature Y?

Generally, there's a changelog. In fact, this (or other "prominent notices" of changes) is required by the GPL! (At least, effectively so for anything with multiple contributors — see GPLv2 section 2a.)

For the GNU coreutils package — and for pretty much everything else from the GNU project directly — this file is definitely the first place to look, and should answer your question 95% of the time.

Why not use the source control afferent to X to search for feature Y? The source repo is the best way to indentify when a particular feature was introduced.

For coreutils you can head to http://git.savannah.gnu.org/cgit/coreutils.git and search for keywords related to Y in log messages or particular lines of code you identified as belonging to Y. You can do that on the web interface directly, or even better, clone the source repo to your station and search using git-bisect, git-blame and git-log --grep.

Then Use git-describe to find out tag is the closest to a specific commmit. Tags are used for version numbers mostly, thus it will give you the version that introduced the commit.

You can adapt the above method, depending on X and it's source control.