This paper proposes a novel approach for smoothing surfaces represented by triangular meshes in a haptic environment. The proposed method is a two-step procedure: surface normal smoothing through fuzzy vector median (FVM) filtering followed by integration of surface normals for vertex position update based on the least absolute error (LAE) criteria. The median and Order Statistic based filters are extensively used in signal processing, especially image processing due to their ability to reject outliers and preserve features such as edges and monotonic regions. More recently, fuzzy ordering theory has been introduced to allow averaging amongst similarly valued samples. This paper extends the fuzzy ordering concept to vector based data and introduces the fuzzy vector median filter. The application of FVM filters to surface normal smoothing yields improved results over previously introduced normal smoothing algorithms. The improved filtering results, coupled with LAE vertex position update, produces surface smoothing that minimizes the effects of noise while simultaneously preserving detail features. Simulation results are presented showing the performance of the proposed method and its advantages over commonly used surface smoothing algorithms. Additionally, optimization procedures for FVM are derived and evaluated.