The palette can be found at 0x35B968, but be careful when changing it as it is shared by both player genders. If you do want to have different palettes for the boy and girl then you can repoint the pointer at either 0x3A5198 (Boy) or 0x3A51C0 (Girl) to some empty space and create a new palette. If you're using JPAN's engine then the male/ female pointers have been changed to 0x1A2440 and 0x1A2468 respectively.
I cannot find it in any map/tileset.
IN R/S/E there are 2 type of grass.. normal grass, and Tall grass.
Using NSE with Fire red i can see the image of the second type of grass, but in advance map can't find it.
Here is an example of the grass i'm refering to (from Emerald):
The tall grass isn't used anywhere in FR so there are no tilesets that use it and the actual tile behaviour that calls the animation is broken. Luckily, knizz found out how to reactivate it in this thread so it is definitely what you're searching for.