Quality of Service (QoS) is one of the important factors to be considered when choosing a Web Service (WS). This paper focuses on performance which is one of the most important QoS attributes. Currently WS recommendation and selection are based on the advertised server-side performance. Since WS clients reside in a heterogeneous environment, performance experienced by clients for the same WS can vary widely. Therefore, WS recommendation based on server-side performance may not be very effective. We propose a WS analysis and recommendation framework that takes into account environment heterogeneity. The analysis framework helps establish WS profiles and client profiles, which are used in the recommendation process to estimate the client-side performance and to determine the most suitable WS provider. By carrying out experiments in the real world (Internet) environment, we demonstrate the fundamental concepts related to client-side performance estimation. Some recommendation scenarios which utilize these estimation techniques are also demonstrated.