I went looking for the Giant's Stone last year (Sep 2009) and found a big erratic at OS grid NJ481290 about where the the stone is marked on early OS maps. Quite a bit higher up tap o' noth than the stone drewbhoy went to.
Quite easy to get to. Follow path from the car park for tap o noth and about half way up from the car park (420m height) head for the trees. It's just inside.
I would be interested to go back and look at the other stone drewbhoy talks about.
Just above the trees is a spur of rock called Clochmaloo (Stone of St Moluag) associated with a famous Celtic missionary from about A.D. 562. well worth a visit too on a nice day.
The Giants Stone is much nearer Newseat Farm than Scardargue it's alternative name and the footprint is very weathered. This was found on the way to the Newseat Cairn heading west from Rhynie on the A941, Cabrach road.
From 'Place Names of Strathbogie' p253 James Macdonlad 1891
Clochmaloo, is a spur of rock jutting out on the side of the Tap o' Noth overlooking Scordarg, and half-way up the Tap. The face of this perpendicular rock is about 30 feet high, and behind, standing clear of the hill, it is 7 or 8 feet high. Two names occur elsewhere which help us to understand this puzzling name. In charters of date 1450, and 1508, we have in the barony of Lochawe, Kilmolew, and in Morvern, Kilmalew, both churches dedicated to Saint Molocus, bishop. The Saint's name usually takes the forms Moluach, Moluoc, Molua, and Molew, which last gives the exact pronunciation as in Clochmaloo. Moluach is patron saint of Mortlach, and at Cloveth (Kildrummie) is Simmerluak's well. Clatt was also dedicated to this saint; and in that parish there was in old times St. Mallach's fair, and there is a farm close to the Kirktown of Clatt called Persylieu, which may contain the saint's name. Tarland is another dedication, and in this parish is Luoch's Fair. We have thus four dedications of Moluach within no great distance from Rhynie, two of them being in the neighbouring parishes; and Clochmaloo, 'the stone of Moluach', suggests the possibility that he was also patron saint of Rhynie. I may notice that clach means 'a stone', and it is unusual to find this word applied to a spur of rock. As it is so used here, it may indicate that the name is artificial, thus differing from all the Gaelic names around it.
A little westward of this rock, and near the base of the cone, is a large boulder called the Giant's stone. The legend connected with it is, that in the days when giants inhabited this part of the world, the giant of Dunnideer made an assault on his brother of the Tap, who, in defending his fort, pitched this great stone from the rampart against the enemy. Dunnideer to show his contempt put out his foot and checked the boulder in its downward course. The stone remains son the very spot it was arrested, and the imprint of the giant's foot may still be seen upon it.
There are many traditional ballads and stories relating to Benachie and Noth. There is a ballad called "John O'Benachie;" and another, "John O'Rhynie, or Jock O'Noth;" and they do not appear in any collection of ancient ballads I have seen.
It is said that long "before King Robert rang," two giants inhabited these mountains, and are supposed to be the respective heroes of the two ballads. These sons of Anak appear to have lived on pretty friendly terms, and to have enjoyed a social crack together, each at his own residence, although distant some ten or twelve miles.
These worthies had another amusement, that of throwing stones at each other; not small pebbles you may believe, but large boulders. On one occasion, however, there appears to have been a coolness between them; for one morning, as he of Noth was returning from a foraging excursion in the district of Buchan, his friend of Benachie, not relishing what he considered an intrusion on his legitimate beat, took up a large stone and threw it at him as he was passing.
Noth, on hearing it rebounding, coolly turned round; and putting himself in a posture of defence, received the ponderous mass on the sole of his foot: and I believe that the stone, with a deeply indented foot-mark on it, is, like the bricks in Jack Cade's chimney, "alive at this day to testify."*
From p286 of Notes and Queries (no204, Sept 24th, 1853).
*this is a quote from Henry the Sixth pt II, act IV, scene II. Jack Cade was an actual rebel against the king in 1450 (regrettably this ended with his head on a pike). A curiously megalithic connection is that he struck the London Stone with his sword to proclaim himself mayor of London.
In describing the vitrified site of the Top of Noth in Strathbogie, Dr Hibbert speaks of "a lofty upright stone on the westerly flank of the hill, connected with which is a monstrous traditional story of its having been placed there by a giant, the print of whose heel in it is still visible." Archaeologia Scotica, vol. iv. p.297.
Mentioned on p 82 of 'Deliciae Literariae: A New Volume of Table-talk', by Joseph Robertson, 1840. (online at Google Books)
The RCAHMS record describes this as a natural stone. A 1967 visit said it was a "large, much-weathered boulder, with a faint natural mark forming the outline of a boot print on its south face".