I was not that annoyed by Feebas. I took my time to fish at every tile until I found a Feebas and spread out my Feebas search over days so it didn't get too frustrating. It's a little nice to have a tiny challenge every now and then. I also agree that the time of day would have been nice, but it was not really necessary.
I felt that all the diving was very tedious and took a lot of time. There were many places to dive, and I thought that it was silly to have to have a Relicanth and Wailord in my team to activate the Regis. I did not enjoy surfing all over the place especially with the slow speed of surf and having to be constantly confronted by Tentacool and other water type pokemon. I'd rather bike quickly, and I don't remember previous generations having such a heavy focus on traveling by water. I guess that means that I was rooting for Team Magma. Overall, the game play was good. It mostly resembled other generations with new moves and new towns but with the same premise of trying to defeat the Elite 4.
I liked the addition of contests and pokeblocks. It added a different element to the pokemon world so that it wasn't just a game about battling and beating the pokemon league. The 2 on 2 battles were also interesting because it allowed new strategies so that pokemon could support each other on the same team. Overall, I was satisfied with the RSE generation, but pokemon games keep improving as with D/P.